Submission #669999

#	Time	Username	Problem	Language	Result	Execution time	Memory
669999		Iliya	Regions (IOI09_regions)	C++17	100 / 100	5426 ms	84272 KiB

regions

/*
 Lemme check my list of powers and weaknesses: 
 ability to do anything, but only whenever I want.
*/
 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int N = 2e5 + 10, R = 3e4, Q = 2e5 + 10, SQ = 499;
int n, r, q, Time, H[N], P[N], St[N], Ft[N], ID[R], cnt[N], Ans[SQ][R];
vector<int> Adj[N], Reg[R], Home[R];
 
void PreDFS(int v){
	St[v] = ++Time;
	Reg[H[v]].push_back(Time);
	for(int u : Adj[v])
		PreDFS(u);
	Ft[v] = Time;
}
 
void DFS(int v){
	if((int) Home[H[v]].size() >= SQ) cnt[ID[H[v]]]++;
	for(int u : Adj[v]){
		for(int i = 1; i < SQ; i++)
			Ans[i][H[u]] += cnt[i];
		DFS(u);
	}
	if((int) Home[H[v]].size() >= SQ) cnt[ID[H[v]]]--;
}
 
void solve(int r1, int r2){
	if((int) Home[r1].size() >= SQ) cout << Ans[ID[r1]][r2] << endl;
	else{
		int Res = 0;
		for(int x : Home[r1]){
			auto X1 = lower_bound(Reg[r2].begin(), Reg[r2].end(), St[x]);
			auto X2 = upper_bound(Reg[r2].begin(), Reg[r2].end(), Ft[x]);
			Res += X2 - X1;
		}
		cout << Res << endl;
	}
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
 
	cin >> n >> r >> q;
	for(int i = 1; i <= n; i++){
		if(i == 1){
			cin >> H[i];
			Home[H[i]].push_back(i);
		}
		else {
			cin >> P[i] >> H[i];
			Adj[P[i]].push_back(i);
			Home[H[i]].push_back(i);
		}
	}
	PreDFS(1);
	int ind = 0;
	for(int i = 1; i <= r; i++)
		if((int) Home[i].size() >= SQ)
			ID[i] = ++ind;
	DFS(1);
	while(q--){
		int r1, r2;
		cin >> r1 >> r2;
		solve(r1, r2);
	}
 
	return 0;
}

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