제출 #365080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365080		crackersamdjam	Regions (IOI09_regions)	C++17	0 / 100	104 ms	48384 KiB

regions

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

#ifndef ONLINE_JUDGE
template<typename T>
void pr(T a){std::cerr<<a<<std::endl;}
template<typename T,typename... Args>
void pr(T a, Args... args) {std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args>
void pr(Args... args){}
#endif

using namespace std;
const int MM = 2e5+5, SQ = 500;

int n, m, q;
vector<int> adj[MM];
int in[MM], out[MM], t;
map<int, int> cnt[MM], parcnt;
int val[MM];
vector<pair<int, int>> down[MM], up[MM];
vector<int> nodes[MM];
int ans[MM], bit[MM];

void update(int i, int v){
	for(; i < MM; i += i&-i)
		bit[i] += v;
}

int query(int i){
	int v = 0;
	for(; i; i -= i&-i)
		v += bit[i];
	return v;
}

void dfs(int cur, int pre){
	in[cur] = ++t;
	for(auto u: adj[cur]){
		if(u == pre) continue;
		dfs(u, cur);
	}
	out[cur] = t;
}

void go(int cur, int pre){
	parcnt[val[cur]]++;
	for(auto [a, i]: up[cur]){
		ans[i] += parcnt[a];
	}

	int id = 0;
	for(auto u: adj[cur]){
		if(u == pre) continue;
		go(u, cur);
		if(size(cnt[u]) > size(cnt[id]))
			id = u;
	}
	cnt[cur] = move(cnt[id]);
	for(auto u: adj[cur]){
		if(u == pre) continue;
		if(u != id){
			for(auto [a, c]: cnt[u]){
				cnt[cur][a] += c;
			}
		}
	}
	cnt[cur][val[cur]]++;
	for(auto [a, i]: down[cur]){
		ans[i] += cnt[cur][a];
	}

	parcnt[val[cur]]--;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>q;
	cin>>val[1];
	nodes[val[1]].emplace_back(1);
	for(int i = 2,p; i <= n; i++){
		cin>>p>>val[i];
		// pr(p, i, val[i]);
		adj[p].emplace_back(i);
		nodes[val[i]].emplace_back(i);
	}
	dfs(1, 0);
	for(int i = 0,a,b; i < q; i++){
		cin>>a>>b;
		// if(size(nodes[a]) > SQ){
		// 	for(int j: nodes[b])
		// 		up[j].emplace_back(a, i);
		// }
		// else if(size(nodes[b]) > SQ){
		// 	for(int j: nodes[a])
		// 		down[j].emplace_back(b, i);
		// }
		// else
		{
			for(int j: nodes[b]){
				update(in[j], 1);
			}
			for(int j: nodes[a]){
				ans[i] += query(out[j]) - query(in[j]-1);
			}
			for(int j: nodes[b]){
				update(in[j], -1);
			}
		}
	}
	// go(1, 0);
	for(int i = 0; i < q; i++)
		cout<<ans[i]<<'\n';
}
/*
for pairs < sqrt, update and query on ett O(n log n)

dfs small to large
O(n log n) for inserting
to query, use small to query for large
O(small*large)
O(n sqrt n)

large to large
O(sqrtn sqrtn) = O(n)

so during dfs, I need one map to store the set of parents and another for subtree (this needs small to large)

*/

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85