제출 #1254834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254834		mngoc._.	Regions (IOI09_regions)	C++20	0 / 100	121 ms	196608 KiB

regions

#include<bits/stdc++.h>
using namespace std;
#define FOR(i , l , r) for(int i = (l) ; i <= (r) ; i++)
#define pii pair<int , int>
const int N = 2e5 + 5;
const int BLOCK = 440;
//Khai Báo
int n , r , q;
int H[N];
vector<int> adj[N];
struct query{
	int r1 ,r2;
} queries[N];
vector<int> adj2[BLOCK];
int cnt[N];
int check[N];
int type[N];
vector<int> c[N];
vector<int> mngoc[BLOCK];
vector<int> cute[N];
int hsh[BLOCK];
vector<pii> qq[N];
int res[N];
//INput?
void input(void){
	cin >> n >> r >> q;
	cin >> H[1];
	cnt[H[1]]++;
	FOR(i , 2 , n){
		int v , x; cin >> v >> x;
		H[i] = x;
		cnt[H[i]]++;
		adj[v].push_back(i);
	}
}

void dfs(int u , int p , int num){
	if(type[u] == num){
		adj2[num].push_back(u);
		return;
	}
	for(auto v : adj[u]){
		if(v == p) continue;
		dfs(v , u , num);
	}
}

void dfs2(int u , int p , int num){
	if(u == num){
		vector<int> tmp;
		for(auto v : adj2[u]){
			dfs2(v , u , num);
			if(tmp.size() < c[v].size()) swap(tmp , c[v]);
			for(auto x : c[u]){
				tmp.push_back(x);
			}
			c[v].clear();
		}
		sort(tmp.begin() , tmp.end());
		mngoc[num] = tmp;
	}
	else{
		c[u].push_back(H[u]);
		for(auto v : adj[u]){
			dfs2(v , u , num);
			if(c[u].size() < c[v].size()) swap(c[u] , c[v]);
			for(auto x : c[v]){
				c[u].push_back(x);
			}
			c[v].clear();
		}
	}
    
}
map<int,int>* kquynh[N];

void dfs3(int u, int p) {
    kquynh[u] = new map<int,int>();
    (*kquynh[u])[H[u]]++;
    for(int v: adj[u]) if (v!=p) {
        dfs3(v, u);
        if(kquynh[u]->size() < kquynh[v]->size()) swap(kquynh[u], kquynh[v]);
        for(auto &pr: *kquynh[v]) {
            (*kquynh[u])[pr.first] += pr.second;
        }
        delete kquynh[v];
    }

    for(auto &qr: qq[H[u]]) {
        int target = qr.first, idx = qr.second;
        res[idx] += (*kquynh[u])[target];
    }
}



void preprocess(void){
	int counter = 0;
	FOR(i , 1 , n){
		if(cnt[H[i]] > BLOCK){
			if(!check[H[i]]){
				check[H[i]] = 1;
				++counter;
				hsh[H[i]] = counter;
			}
			type[i] = counter;	
		} 
	    cute[H[i]].push_back(i);		

	}
	//build cây
	FOR(i , 1 , counter){
		dfs(1 , 0 , i);
	}
	//Build sqrt(n) cây
	FOR(i , 1 , BLOCK - 1){
		if(adj2[i].size() == 0) continue;
	    dfs2(i , 0 , i);   
	}
}

void solve(void){
	FOR(i , 1 , q){
		int r1 , r2; cin >> r1 >> r2;
		if(cnt[r1] > BLOCK){
			int pos1 = lower_bound(mngoc[hsh[r1]].begin(), mngoc[hsh[r1]].end() , r2) - mngoc[hsh[r1]].begin();
			int pos2 = upper_bound(mngoc[hsh[r1]].begin() , mngoc[hsh[r1]].end() , r2) - mngoc[hsh[r1]].begin();
			res[i] = pos2 - pos1;
		}
		else{
			qq[r1].push_back({r2 , i});
		}
	}
	dfs3(1 , 0);
	FOR(i , 1 , q){
		cout << res[i] << '\n';
	}
	
	
}

signed main(void){
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	input();
    preprocess();
	solve();
	
	return 0;
}

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