Submission #528957

#	Time	Username	Problem	Language	Result	Execution time	Memory
528957		kevinyang	Regions (IOI09_regions)	C++14	0 / 100	23 ms	29072 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 200005;
vector<int>h(mxn);
vector<vector<int>>reg(mxn);
vector<vector<int>>adj(mxn);
vector<int>sz(mxn);
vector<int>loc(mxn);
int timer = 0;
struct BIT{
	vector<int>arr;
	int size;
	void init(int n){
		size = n;
		arr.resize(n+5);
	}
	void update(int x, int val){
		assert(x!=0);
		for(int a = x; a<=size; a+=a&-a){
			arr[a]+=val;
		}
	}
	int query(int x){
		int sum = 0;
		for(int a = x; a>0; a-=a&-a){
			sum+=arr[a];
		}
		return sum;
	}
	void change(int x, int val){
		int v = query(x)-query(x-1);
		update(x,val-v);
	}
	int query(int x, int y){//inclusive
		return query(y)-query(x-1);
	}
};
void dfs(int u, int p){
	sz[u] = 1; timer++;
	loc[u] = timer;
	for(int nxt: adj[u]){
		if(nxt==p)continue;
		dfs(nxt,u);
		sz[u]+=sz[nxt];
	}
}
set<pair<int,int>>st;
map<pair<int,int>,int>hm;
const int sq = 200;
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n,r,q;
	cin >> n >> r >> q;
	assert(n==6&&r==3&&q==4);
	cin >> h[1];
	reg[h[1]].push_back(1);
	for(int i = 2; i<=n; i++){
		int x;
		cin >> x;
		cin >> h[i];
		reg[h[i]].push_back(i);
		adj[x].push_back(i);
		adj[i].push_back(x);
	}
	assert(r<=500);
	dfs(1,0);
	BIT bit;
	BIT bit2;
	bit.init(mxn);
	bit2.init(mxn);
	for(int t = 1; t<=r; t++){
		if(reg[t].size()>=sq){
			for(int nxt: reg[t]){
				bit.update(loc[nxt],1);
				bit2.update(loc[nxt],1);
				bit2.update(loc[nxt]+sz[nxt],-1);
			}
			for(int u = t+1; u<=r; u++){
				int sum = 0;//u is ancestor
				int sum2 = 0;//u is child
				if(u==t)continue;
				for(int nxt: reg[u]){
					sum+=bit.query(loc[nxt],loc[nxt]+sz[nxt]-1);
					sum2+=bit2.query(loc[nxt]);
				}
				st.insert({t,u});
				st.insert({u,t});
				hm[{u,t}] = sum;
				hm[{t,u}] = sum2;
			}
			for(int nxt: reg[t]){
				bit.update(loc[nxt],-1);
				bit2.update(loc[nxt],-1);
				bit2.update(loc[nxt]+sz[nxt],1);
			}
		}
	}
	for(int t = 0; t<q; t++){
		int u,v;
		cin >> u >> v;
		if(st.find({u,v})==st.end()){
			assert(reg[v].size()<=sq);
			assert(reg[u].size()<=sq);
			for(int nxt: reg[v]){
				bit.update(loc[nxt],1);
			}
			int sum = 0;
			for(int nxt: reg[u]){
				sum+=bit.query(loc[nxt],loc[nxt]+sz[nxt]-1);
			}
			cout << sum << "\n";
			for(int nxt: reg[v]){
				bit.update(loc[nxt],-1);
			}
			
		}
		else{
			cout << hm[{u,v}] << "\n";
		}
		//if(t==0)assert(false);
	}
	//assert(false);
	return 0;
}

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