제출 #1254835

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254835		mngoc._.	Regions (IOI09_regions)	C++20	0 / 100	2224 ms	75680 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];
vector<int>* st[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 (type[u] == num) {
        st[u] = new vector<int>();
    } else {
        st[u] = new vector<int>(1, H[u]);
    }
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs2(v, u, num);
        if (st[v]->empty()) continue;
        if (st[u]->size() < st[v]->size()) swap(st[u], st[v]);
        st[u]->insert(st[u]->end(),st[v]->begin(), st[v]->end());
        st[v]->clear();
    }
    if (type[u] == num) {
        auto &vec = *st[u];
        sort(vec.begin(), vec.end());
        mngoc[num] = vec;      
    }
}

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){
		for(int u : adj2[i]) {
           if (st[u]) { st[u]->clear(); delete st[u]; st[u]=nullptr; }
        }
		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