返回信息流我用多叉树的父亲表示法，即 tree[i] = i_parent 存储。删除时置 -1，查找时不断向上到 0 则成功，答案超时。我看统计结果中最短只要 5ms，请问可以用什么高效的数据结构呢？
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #92392同步于 2017/3/15
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
OJ-268 进程管理
yjc120592
2017/3/15镜像同步6 回复
订阅后，新回复会通过你的通知中心匿名送达。
6 条回复
#include <stdio.h>
struct process {
bool mark;
bool son[101];
}buf[101];
void create(int a) {
buf[a].mark = true;
for (int i = 0; i < 101; i++) {
buf[a].son[i] = false;
}
}
void kill(int a) {
buf[a].mark = false;
for (int i = 0; i < 101; i++) {
if (buf[a].son[i]) {
kill(i);
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
create(0);
for (int i = 1; i < 101; i++) {
buf[i].mark = false;
}
int n;
scanf("%d", &n);
while (n--) {
char str[20];
scanf("%s", str);
if (str[0] == 'F') {
int a, b;
scanf("%d%d", &a, &b);
buf[a].son[b] = true;
if (!buf[b].mark) create(b);
}
else if (str[0] == 'Q') {
int a;
scanf("%d", &a);
if (buf[a].mark) printf("Yes\n");
else printf("No\n");
}
else {
int a;
scanf("%d", &a);
kill(a);
buf[0].mark = true;
}
}
}
return 0;
}
【 在 yjc120592 的大作中提到: 】
: 我用多叉树的父亲表示法，即 tree[i] = i_parent 存储。删除时置 -1，查找时不断向上到 0 则成功，答案超时。我看统计结果中最短只要 5ms，请问可以用什么高效的数据结构呢？
【 在 chenxiansf 的大作中提到: 】
谢谢，看来必须用多叉树的孩子表示法。结合之前做过的此类题，我感觉北邮 OJ 的查找题，测试用例都属于“查找繁忙型”，应该让查找时间复杂度为 O(1)。但如果是“增删繁忙型”，这种方法就不太高效了。你觉得呢？
感觉有道理
【 在 yjc120592 的大作中提到: 】
:
: 谢谢，看来必须用多叉树的孩子表示法。结合之前做过的此类题，我感觉北邮 OJ 的查找题，测试用例都属于“查找繁忙型”，应该让查找时间复杂度为 O(1)。但如果是“增删繁忙型”，这种方法就不太高效了。你觉得呢？
【 在 viredery 的大作中提到: 】
: 如果是0->1->2，删了1又增加了1，此时查找2呢
2 不存在。另外题目有限定，被 kill 的进程不会再 fork