Submission #1170492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170492		ZeroCool	Regions (IOI09_regions)	C++20	35 / 100	6496 ms	40620 KiB

regions

#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define ar array
#define ld long double
#define int long long
#define all(v) v.begin(), v.end()

const int N = 2e5 + 20;
const int K = 469;
const int LOG = 26;
const int INF = 1e12;	
const int MOD = 998244353;

int A[N];
vector<int> g[N];
int n;
int T = -1;
int in[N], out[N];
map<int, vector<int> > mp1;//Teminja
map<int, vector<int> > mp2;//Vreminja

void dfs(int x){
	in[x] = ++T;
	mp1[A[x]].push_back(x);
	mp2[A[x]].push_back(in[x]);
	for(auto u: g[x])dfs(u);
	out[x] = T;
}

vector<vector<int>> ans;
int ind[N];
void dfs2(int x,int c,int cnt = 0){
	cnt += (A[x] == c);
	for(auto u: g[x]){
		ans.back()[A[x]] += cnt;
		dfs2(u, c, cnt);
	}
}

void orz(){
	int r, q;
	
	cin>>n>>r>>q;
	cin>>A[0];
	--A[0];
	for(int i = 1;i < n;i++){
		int x, y;
		cin>>x>>y;
		--x, --y;
		g[x].push_back(i);
		A[i] = y;
	}
	dfs(0);
	for(int i = 0;i < r;i++){
		ind[i] = -1;
		if(mp1[i].size() < K)continue;
		ind[i] = ans.size();
		ans.push_back(vector<int>(r, 0));
		dfs2(0, i, 0);
	}
	while(q--){
		int a, b;
		cin>>a>>b;
		--a, --b;
		if(mp1[a].size() >= K)cout<<ans[ind[a]][b]<<endl;
		else{
			int ans = 0;
			for(auto u: mp1[a]){
				int c = upper_bound(all(mp2[b]), out[u]) - upper_bound(all(mp2[b]), in[u]);
				ans += c;
			}
			cout<<ans<<endl;
		}
	}
}	
signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int t;
	//cin>>t;
	t = 1;
	while(t--)orz();
}
	

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