Submission #1175776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175776		mertbbm	Regions (IOI09_regions)	C++20	40 / 100	8101 ms	172748 KiB

regions

#include <bits/stdc++.h>
using namespace std;

//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

const int blk=1000;
vector<int>adj[200005];
int in[200005];
int out[200005];
int arr[200005];
int ptr=0;
vector<int>order;

void dfs(int index, int par){
	in[index]=++ptr;
	order.push_back(index);
	for(auto it:adj[index]){
		if(it==par) continue;
		dfs(it,index);
	}
	out[index]=ptr;
}

int val[605][200005];

void dfs2(int index, int color, int cur, int ptr, int par){
	if(arr[index]==color) cur++;
	else val[ptr][arr[index]]+=cur;
	for(auto it:adj[index]){
		if(it==par) continue;
		dfs2(it,color,cur,ptr,index);
	}
}

//persistent segment tree
inline int combine(int a, int b){
	return a+b;
}

struct node{
	int s,e,m;
	node *l,*r;
	int v;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	node(node *u){
		s=u->s,e=u->e,m=u->m,v=u->v,l=u->l,r=u->r;
	}
	
	void upd(int x, int y){
		if(s==e){
			v+=y;
			return;
		}
		if(x<=m){
			l=new node(l);
			l->upd(x,y);
		}
		else{
			r=new node(r);
			r->upd(x,y);
		}
		v=combine(l->v,r->v);
	}
	
	int query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		if(y<=m) return l->query(x,y);
		if(x>m) return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
}*root[200005];

vector<int>storage[200005];

void solve(){
	int n,m,q;
	cin >> n >> m >> q;

	int cnt[m+5];
	memset(cnt,0,sizeof(cnt));
	int temp,temp2;
	cin >> arr[1];
	cnt[arr[1]]++;
	storage[arr[1]].push_back(1);
	for(int x=2;x<=n;x++){
		cin >> temp >> temp2;
		arr[x]=temp2;
		adj[x].push_back(temp);
		adj[temp].push_back(x);
		cnt[arr[x]]++;
		storage[arr[x]].push_back(x);
	}
	
	order.push_back(0);
	dfs(1,-1);
	//show4(order,order);
	
	int hash[m+5];
	int counter=0;
	for(int x=1;x<=m;x++){
		if(cnt[x]>blk){
			dfs2(1,x,0,counter,-1);
			hash[x]=counter++;
		}
	}
	
	root[0]=new node(0,m+5);
	for(int x=1;x<=n;x++){
		root[x]=new node(root[x-1]);
		if(cnt[arr[order[x]]]<=blk){
			root[x]->upd(arr[order[x]],1);
		}
	}
	
	for(int x=0;x<q;x++){
		cin >> temp >> temp2;
		if(cnt[temp]>blk){
			int ans=val[hash[temp]][temp2];
			cout << ans << endl;
		}
		else{
			int ans=0;
			for(auto it:storage[temp]){
				//show(it,it);
				//show2(temp,temp,temp2,temp2);
				//show2(in[it],in[it],out[it],out[it]);
				ans+=root[out[it]]->query(temp2,temp2)-root[in[it]-1]->query(temp2,temp2);
				//show(it2,it);
			}
			cout << ans << endl;
		}
	}
}
																   
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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