답안 #41117 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41117	2018-02-13T01:01:31 Z	14kg	트리 (KOI16_tree)	C++11	100 / 100	409 ms	65536 KB

tree

#include <stdio.h>
#include <vector>
#define NN 262144
#define INF 999999999

using namespace std;
struct Node {
	int s, e, up;
} node[200001];
vector<int> r[200001];
int n, nn, q, tree_cnt, tree[NN * 2];

int max2(int x, int y) { return x > y ? x : y; }
void make_tree(int x, int up) {
	node[x].up = up, node[x].s = ++tree_cnt;
	for (auto i : r[x])
		if (i != up) make_tree(i, x);
	node[x].e = tree_cnt;
}
int get_top(int x) {
	if (x == 1) return tree[1];
	return max2(tree[x], get_top(x / 2));
}
void tree_push(int lev, int l, int r, int x, int y, int num) {
	int mid = (l + r) / 2;
	
	if (x <= l && r <= y) { tree[lev] = max2(tree[lev], num); return; }
	if (r < x || y < l) return;
	tree_push(lev * 2, l, mid, x, y, num), tree_push(lev * 2 + 1, mid + 1, r, x, y, num);
}
int main() {
	int x, y, z;

	scanf("%d %d", &n, &q);
	for (nn = 1; nn < n; nn *= 2);
	for (int i = 2; i <= n; i++) {
		scanf("%d", &x);
		r[i].push_back(x), r[x].push_back(i);
	}

	make_tree(1, 0), tree[1] = 1;
	while (q--) {
		scanf("%d %d %d", &x, &y, &z);

		int tx = get_top(node[x].s + nn - 1), ty = get_top(node[y].s + nn - 1);
		printf("%s\n", tx == ty ? "YES" : "NO");

		if (z && tx == ty) tree_push(1, 1, nn, node[x].s, node[x].e, node[x].s);
		if (z && tx != ty) tree_push(1, 1, nn, node[y].s, node[y].e, node[y].s);
	}
}

Compilation message

tree.cpp: In function 'int main()':
tree.cpp:34:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
                        ^
tree.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^
tree.cpp:43:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &z);
                                ^

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5124 KB	Output is correct
2	Correct	6 ms	5124 KB	Output is correct
3	Correct	6 ms	5264 KB	Output is correct
4	Correct	6 ms	5308 KB	Output is correct
5	Correct	6 ms	5340 KB	Output is correct
6	Correct	6 ms	5356 KB	Output is correct
7	Correct	6 ms	5372 KB	Output is correct
8	Correct	6 ms	5580 KB	Output is correct
9	Correct	6 ms	5640 KB	Output is correct
10	Correct	7 ms	5780 KB	Output is correct

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5124 KB	Output is correct
2	Correct	6 ms	5124 KB	Output is correct
3	Correct	6 ms	5264 KB	Output is correct
4	Correct	6 ms	5308 KB	Output is correct
5	Correct	6 ms	5340 KB	Output is correct
6	Correct	6 ms	5356 KB	Output is correct
7	Correct	6 ms	5372 KB	Output is correct
8	Correct	6 ms	5580 KB	Output is correct
9	Correct	6 ms	5640 KB	Output is correct
10	Correct	7 ms	5780 KB	Output is correct
11	Correct	6 ms	5780 KB	Output is correct
12	Correct	6 ms	5780 KB	Output is correct
13	Correct	6 ms	5780 KB	Output is correct
14	Correct	7 ms	5780 KB	Output is correct
15	Correct	6 ms	5780 KB	Output is correct
16	Correct	6 ms	5780 KB	Output is correct
17	Correct	6 ms	5780 KB	Output is correct
18	Correct	6 ms	5780 KB	Output is correct
19	Correct	7 ms	5792 KB	Output is correct
20	Correct	6 ms	5808 KB	Output is correct
21	Correct	6 ms	5828 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5124 KB	Output is correct
2	Correct	6 ms	5124 KB	Output is correct
3	Correct	6 ms	5264 KB	Output is correct
4	Correct	6 ms	5308 KB	Output is correct
5	Correct	6 ms	5340 KB	Output is correct
6	Correct	6 ms	5356 KB	Output is correct
7	Correct	6 ms	5372 KB	Output is correct
8	Correct	6 ms	5580 KB	Output is correct
9	Correct	6 ms	5640 KB	Output is correct
10	Correct	7 ms	5780 KB	Output is correct
11	Correct	6 ms	5780 KB	Output is correct
12	Correct	6 ms	5780 KB	Output is correct
13	Correct	6 ms	5780 KB	Output is correct
14	Correct	7 ms	5780 KB	Output is correct
15	Correct	6 ms	5780 KB	Output is correct
16	Correct	6 ms	5780 KB	Output is correct
17	Correct	6 ms	5780 KB	Output is correct
18	Correct	6 ms	5780 KB	Output is correct
19	Correct	7 ms	5792 KB	Output is correct
20	Correct	6 ms	5808 KB	Output is correct
21	Correct	6 ms	5828 KB	Output is correct
22	Correct	133 ms	8784 KB	Output is correct
23	Correct	136 ms	10880 KB	Output is correct
24	Correct	141 ms	13204 KB	Output is correct
25	Correct	150 ms	15276 KB	Output is correct
26	Correct	137 ms	17520 KB	Output is correct
27	Correct	122 ms	19868 KB	Output is correct
28	Correct	117 ms	22092 KB	Output is correct
29	Correct	117 ms	24412 KB	Output is correct
30	Correct	112 ms	26648 KB	Output is correct
31	Correct	113 ms	28740 KB	Output is correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5124 KB	Output is correct
2	Correct	6 ms	5124 KB	Output is correct
3	Correct	6 ms	5264 KB	Output is correct
4	Correct	6 ms	5308 KB	Output is correct
5	Correct	6 ms	5340 KB	Output is correct
6	Correct	6 ms	5356 KB	Output is correct
7	Correct	6 ms	5372 KB	Output is correct
8	Correct	6 ms	5580 KB	Output is correct
9	Correct	6 ms	5640 KB	Output is correct
10	Correct	7 ms	5780 KB	Output is correct
11	Correct	351 ms	52440 KB	Output is correct
12	Correct	364 ms	56692 KB	Output is correct
13	Correct	356 ms	61004 KB	Output is correct
14	Correct	368 ms	65276 KB	Output is correct
15	Correct	336 ms	65536 KB	Output is correct
16	Correct	352 ms	65536 KB	Output is correct
17	Correct	387 ms	65536 KB	Output is correct
18	Correct	378 ms	65536 KB	Output is correct
19	Correct	409 ms	65536 KB	Output is correct
20	Correct	382 ms	65536 KB	Output is correct
21	Correct	395 ms	65536 KB	Output is correct

Subtask #5
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5124 KB	Output is correct
2	Correct	6 ms	5124 KB	Output is correct
3	Correct	6 ms	5264 KB	Output is correct
4	Correct	6 ms	5308 KB	Output is correct
5	Correct	6 ms	5340 KB	Output is correct
6	Correct	6 ms	5356 KB	Output is correct
7	Correct	6 ms	5372 KB	Output is correct
8	Correct	6 ms	5580 KB	Output is correct
9	Correct	6 ms	5640 KB	Output is correct
10	Correct	7 ms	5780 KB	Output is correct
11	Correct	6 ms	5780 KB	Output is correct
12	Correct	6 ms	5780 KB	Output is correct
13	Correct	6 ms	5780 KB	Output is correct
14	Correct	7 ms	5780 KB	Output is correct
15	Correct	6 ms	5780 KB	Output is correct
16	Correct	6 ms	5780 KB	Output is correct
17	Correct	6 ms	5780 KB	Output is correct
18	Correct	6 ms	5780 KB	Output is correct
19	Correct	7 ms	5792 KB	Output is correct
20	Correct	6 ms	5808 KB	Output is correct
21	Correct	6 ms	5828 KB	Output is correct
22	Correct	133 ms	8784 KB	Output is correct
23	Correct	136 ms	10880 KB	Output is correct
24	Correct	141 ms	13204 KB	Output is correct
25	Correct	150 ms	15276 KB	Output is correct
26	Correct	137 ms	17520 KB	Output is correct
27	Correct	122 ms	19868 KB	Output is correct
28	Correct	117 ms	22092 KB	Output is correct
29	Correct	117 ms	24412 KB	Output is correct
30	Correct	112 ms	26648 KB	Output is correct
31	Correct	113 ms	28740 KB	Output is correct
32	Correct	351 ms	52440 KB	Output is correct
33	Correct	364 ms	56692 KB	Output is correct
34	Correct	356 ms	61004 KB	Output is correct
35	Correct	368 ms	65276 KB	Output is correct
36	Correct	336 ms	65536 KB	Output is correct
37	Correct	352 ms	65536 KB	Output is correct
38	Correct	387 ms	65536 KB	Output is correct
39	Correct	378 ms	65536 KB	Output is correct
40	Correct	409 ms	65536 KB	Output is correct
41	Correct	382 ms	65536 KB	Output is correct
42	Correct	395 ms	65536 KB	Output is correct
43	Correct	293 ms	65536 KB	Output is correct
44	Correct	293 ms	65536 KB	Output is correct
45	Correct	294 ms	65536 KB	Output is correct
46	Correct	265 ms	65536 KB	Output is correct
47	Correct	318 ms	65536 KB	Output is correct
48	Correct	217 ms	65536 KB	Output is correct
49	Correct	212 ms	65536 KB	Output is correct
50	Correct	215 ms	65536 KB	Output is correct
51	Correct	395 ms	65536 KB	Output is correct

답안 #41117

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 13.0 / 13.0

Subtask #3 14.0 / 14.0

Subtask #4 19.0 / 19.0

Subtask #5 45.0 / 45.0

Subtask #1
9.0 / 9.0

Subtask #2
13.0 / 13.0

Subtask #3
14.0 / 14.0

Subtask #4
19.0 / 19.0

Subtask #5
45.0 / 45.0