Submission #27172

#	Time	Username	Problem	Language	Result	Execution time	Memory
27172		wwiiiii	트리 (KOI16_tree)	C++14	100 / 100	1186 ms	32540 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;
	queue<int> q; q.push(node);
	while (!q.empty())
	{
		int now = q.front(); q.pop();
		for (auto next : adj[now]) {
			if (treeidx[next] != maxidx) {
				treeidx[next] = maxidx;
				q.push(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()) {
		if(qnow != -1 && qit != adj[qnow].end()){
			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()) {
		if (pqnow != -1 && pqit != adj[pqnow].end()) {
			visited[*pqit] = visitmax;
			pq.push(*pqit); pqit++;
		}
	}

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

	parent[node] = node;

}

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	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:76: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:78:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &parent[i]);
                          ^
tree.cpp:83: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: 19 / 19
• Subtask 5: 45 / 45