Submission #41117

#	Time	Username	Problem	Language	Result	Execution time	Memory
41117		14kg	트리 (KOI16_tree)	C++11	100 / 100	409 ms	65536 KiB

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 (stderr)

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 / 9
• Subtask 2: 13 / 13
• Subtask 3: 14 / 14
• Subtask 4: 19 / 19
• Subtask 5: 45 / 45