Submission #27155

#	Time	Username	Problem	Language	Result	Execution time	Memory
27155		wwiiiii	트리 (KOI16_tree)	C++14	36 / 100	2000 ms	38536 KiB

tree

#include <cstdio>
#include <vector>
#include <queue>
#include <set>
using namespace std;
const int N = 200100;
set<int> adj[N];
int parent[N];
int treeidx[N];
int n, q, maxidx, visitmax;
int visited[N];
void reindex(int node) {
	treeidx[node] = maxidx;
	for (auto next : adj[node]) {
		if (treeidx[next] != maxidx) {
			treeidx[next] = maxidx;
			reindex(next);
		}
	}
}

void cut(int node)
{
	visitmax++;
	if (node == parent[node]) return;
	adj[node].erase(parent[node]);
	adj[parent[node]].erase(node);
	queue<int> q, pq;
	q.push(node); pq.push(parent[node]);
	int qnow = -1, pqnow = -1;
	set<int>::iterator qit, pqit;
	while ((!q.empty()) && (!pq.empty()))
	{
		while (qnow == -1 || qit == adj[qnow].end()) {
			if (q.empty()) break;
			qnow = q.front(); q.pop();
			qit = adj[qnow].begin();
			while (qit != adj[qnow].end() && visited[*qit] == visitmax) qit++;
		}
		if (!q.empty()) {
			visited[*qit] = visitmax;
			q.push(*qit); qit++;
		}
		while (pqnow == -1 || pqit == adj[pqnow].end()) {
			if (pq.empty()) break;
			pqnow = pq.front(); pq.pop();
			pqit = adj[pqnow].begin();
			while (pqit != adj[pqnow].end() && visited[*pqit] == visitmax) pqit++;
		}
		if (!pq.empty()) {
			visited[*qit] = visitmax;
			pq.push(*pqit); pqit++;
		}
	}

	maxidx++;
	if (q.empty()) reindex(node);
	else reindex(parent[node]);

	parent[node] = node;

}

int main()
{
	scanf("%d %d", &n, &q);
	for (int i = 2; i <= n; i++) {
		scanf("%d", &parent[i]);
		adj[parent[i]].insert(i);
		adj[i].insert(parent[i]);
	}
	while (q--) {
		int b, c, d; scanf("%d %d %d", &b, &c, &d);
		switch (d)
		{
		case 0:
			puts(treeidx[b] == treeidx[c] ? "YES" : "NO"); break;
		case 1:
			if (treeidx[b] == treeidx[c])
			{
				puts("YES"); cut(b);
			}
			else
			{
				puts("NO"); cut(c);
			}
		}
	}
}

Compilation message (stderr)

tree.cpp: In function 'int main()':
tree.cpp:66: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:68:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &parent[i]);
                          ^
tree.cpp:73:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int b, c, d; scanf("%d %d %d", &b, &c, &d);
                                             ^

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 14 / 14
• Subtask 4: 0 / 19
• Subtask 5: 0 / 45