Submission #1123986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123986		Saul0906	Regions (IOI09_regions)	C++17	1 / 100	232 ms	31004 KiB

regions

#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a:b)
#define pb push_back
#define ppb pop_back
#define pii pair<int, int>
#define fi first
#define se second
#define mid ((l+r)>>1)
#define all(a) a.begin(),a.end()

using namespace std;

const int B=500, MAXN=2e5+5, MAXR=2.5e4+5;
int tin[MAXN], tout[MAXN], val[B][MAXR], h[MAXN], ind[MAXR], n, r, q, idx, timer;
vector<int> adj[MAXN], vert[MAXR];
vector<pii> nodes[MAXR];

void dfs(int u, int c, int i){
	if(h[u]==i) c++;
	repa(v,adj[u]) dfs(v,c,i);
	val[ind[i]][h[u]]+=c;
}

void dfs_euler(int u){
	tin[u]=timer++;
	repa(v,adj[u]) dfs_euler(v);
	tout[u]=timer++;
}

bool comp(pii a, pii b){
	return a.se<b.se;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>r>>q;
	cin>>h[1];
	rep(i,2,n+1){
		int p;
		cin>>p>>h[i];
		adj[p].pb(i);
	}
	fill(ind,ind+MAXR,B+5);
	dfs_euler(1);
	rep(i,1,n+1){
		nodes[h[i]].pb({tin[i],tout[i]});
		vert[h[i]].pb(i);
	}
	rep(i,1,r+1){
		if(nodes[i].size()>B){
			ind[i]=idx++;
			dfs(1,0,i);
		}
	}
	rep(i,1,n+1) sort(all(nodes[i]),comp); 
	while(q--){
		int r1, r2;
		cin>>r1>>r2;
		if(ind[r1]<B) cout<<val[ind[r1]][r2]<<endl;
		else{
			int sum=0;
			repa(e,vert[r1]){
				int l=0, r=nodes[r2].size()-1, L, R;
				while(l<=r){
					if(nodes[r2][mid].fi<tin[e]) l=mid+1;
					else r=mid-1;
				}
				L=l;
				l=0, 
				r=nodes[r2].size()-1;
				while(l<=r){
					if(nodes[r2][mid].se<=tout[e]) l=mid+1;
					else r=mid-1;
				}
				R=r;
				sum+=max(R-L+1,0);
			}
			cout<<sum<<endl;
		}
	}
}

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