Submission #27171

#	Time	Username	Problem	Language	Result	Execution time	Memory
27171		topology	트리 (KOI16_tree)	C++14	100 / 100	789 ms	54928 KiB

tree

#include <bits/stdc++.h>
#ifdef TOPOLOGY
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif
using namespace std;

struct fenwick {
	vector<int> tree;
	int n;
	fenwick(int n_){
		n = n_;
		tree.resize(n+1);
	}
	void upd(int i){
		assert(i);
		while (i <= n){
			tree[i]++;
			i += i&-i;
		}
	}
	int sum(int i){
		int res = 0;
		while (i){
			res += tree[i];
			i -= i&-i;
		}
		return res;
	}
};

int n, q, par[200003][20], depth[200003], hidx[200003], subsz[200003];
vector<int> graph[200003];
vector<vector<int> > heavy;
vector<fenwick> trees;

int dfs(int node, int p){
	for (int i=1; i<20; i++){
		par[node][i] = par[par[node][i-1]][i-1];
	}
	subsz[node] = 1;
	for (auto &nxt : graph[node]){
		if (p == nxt) continue;
		depth[nxt] = depth[node] + 1;
		subsz[node] += dfs(nxt, node);
	}
	return subsz[node];
}

int lca(int u, int v){
	if (depth[u] > depth[v]) swap(u, v);
	int dif = depth[v] - depth[u];
	for (int i=0; (1<<i)<=dif; i++){
		if (dif & (1<<i)){
			v = par[v][i];
		}
	}
	if (u == v) return u;
	for (int i=19; i>=0; i--){
		if (par[u][i] != par[v][i]){
			u = par[u][i];
			v = par[v][i];
		}
	}
	return par[u][0];
}

void hld(){
	queue<int> q;
	for (auto &nxt : graph[1]){
		q.push(nxt);
	}
	while (!q.empty()){
		int node = q.front(); q.pop();
		for (auto &nxt : graph[node]){
			if (nxt == par[node][0]) continue;
			q.push(nxt);
		}
		if (subsz[node]*2 >= subsz[par[node][0]] && par[node][0] != 1){
			int ppi = hidx[par[node][0]];
			heavy[ppi].push_back(node);
			hidx[node] = ppi;
		}
		else {
			hidx[node] = (int) heavy.size();
			vector<int> tmp = {par[node][0], node};
			heavy.push_back(tmp);
		}
	}
}

int query(int u, int v){
	if (u == v) return 0;
	int uidx = hidx[u], vidx = hidx[v];
	if (uidx == vidx){
		int rt = heavy[uidx][0];
		return trees[uidx].sum(depth[v]-depth[rt]) - trees[vidx].sum(depth[u]-depth[rt]);
	}
	return query(u, heavy[vidx][0]) + trees[vidx].sum(depth[v]-depth[heavy[vidx][0]]);
}

void cut(int u){
	if (u == 1) return;
	int uidx = hidx[u];
	trees[uidx].upd(depth[u] - depth[heavy[uidx][0]]);
}

int main(){
	scanf("%d%d", &n, &q);
	for (int i=0; i<n-1; i++){
		int u;
		scanf("%d", &u);
		par[i+2][0] = u;
		graph[u].push_back(i+2);
	}
	dfs(1, -1);
	hld();
	for (auto &v : heavy){
		fenwick fen(v.size());
		trees.push_back(fen);
	}
	for (int i=0; i<q; i++){
		int b, c, d;
		scanf("%d%d%d", &b, &c, &d);
		int l = lca(b, c);
		if (!d){
			if (query(l, c) || query(l, b)) puts("NO");
			else puts("YES");
		}
		else {
			if (query(l, c) || query(l, b)){
				puts("NO");
				cut(c);
			}
			else {
				puts("YES");
				cut(b);
			}
		}
	}
	return 0;
}

Compilation message (stderr)

tree.cpp: In function 'int main()':
tree.cpp:110:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
                       ^
tree.cpp:113:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &u);
                  ^
tree.cpp:125:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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