제출 #1248213

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248213		g4yuhg	Regions (IOI09_regions)	C++20	0 / 100	81 ms	26100 KiB

regions

//Huyduocdithitp
//minhpk chi toi thuat
#include <bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 200005
using namespace std;

bool ghuy4g;

const ll S = 500;

ll n, r, q, h[N], s[N], in[N], out[N], timeDfs;
int f[S + 2][25002], mp[N], cur;
int cnt[S + 2];
vector<ll> adj[N];
vector<ll> vt[25002];

void dfs(ll u) {
	//cout << u << " " << timeDfs + 1 << endl;
	in[u] = ++ timeDfs;
	if (mp[h[u]]) {
		cnt[mp[h[u]]] ++ ;
	}
	for (int i = 1; i <= cur; i ++) {
		f[i][h[u]] += cnt[i];
	}
	for (auto v : adj[u]) {
		dfs(v);
	}
	out[u] = timeDfs;
	if (mp[h[u]]) {
		cnt[mp[h[u]]] -- ;
	}
}

bool cmp(ll u, ll v) {
	if (in[u] != in[v]) {
		return in[u] < in[v];
	}
	return out[u] < out[v];
}

void solve(ll r1, ll r2) {
	// tim thang dau tien co
	ll res = 0;
	for (auto u : vt[r1]) {
		// tim thang v sao cho in[u] <= in[v] <= out[u];
		ll l = 0, r = vt[r2].size() - 1, ans = -1;
		while (l <= r) {
			ll mid = (l + r) / 2;
			if (in[u] <= in[vt[r2][mid]]) {
				ans = mid;
				r = mid - 1;
			}
			else {
				l = mid + 1;
			}
		}
		if (ans == -1) {
			continue;
		}
		ll ans_l = ans;
		l = ans, r = vt[r2].size() - 1, ans = -1;
		while (l <= r) {
			ll mid = (l + r) / 2;
			if (in[vt[r2][mid]] <= out[u]) {
				ans = mid;
				l = mid + 1;
			}
			else {
				r = mid - 1;
			}
		}
		if (ans == -1) {
			continue;
		}
		res += ans - ans_l + 1;
	}
	cout << res << endl;
}

bool klinh;

signed main(void) {
    faster;
    cin >> n >> r >> q;
    
    for (int i = 1; i <= n; i ++) {
    	if (i == 1) {
    		cin >> h[i];
    		vt[h[i]].push_back(i);
    		continue;	
    	}
    	cin >> s[i] >> h[i];
    	adj[s[i]].push_back(i);
    	vt[h[i]].push_back(i);
    }
    dfs(1);
    for (int i = 1; i <= r; i ++) {
    	sort(vt[i].begin(), vt[i].end(), cmp);
    	if (vt[i].size() > S) {
    		mp[i] = ++ cur;
    	}	
    }
    dfs(1);
    for (int i = 1; i <= q; i ++) {
    	ll r1, r2;
    	cin >> r1 >> r2;
    	if (vt[r1].size() > S) {
    		cout << f[mp[r1]][r2] << endl;
    	}
    	else {
    		//cout << i << " : ";
    		solve(r1, r2);
    	}
    }
    
    
    cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
    return 0;
}

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