Submission #733414

#	Time	Username	Problem	Language	Result	Execution time	Memory
733414		penguin133	Regions (IOI09_regions)	C++17	100 / 100	4901 ms	66324 KiB

regions

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

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, r, q;
map <int, int> cur;
vector <int> adj[200005];
int A[200005];
map <int, int> fin[25005];
int S[200005], E[200005];
const int sz = 500;
int big[25005];
vector <int> stuf[25005], stuf2[25005];
void dfs(int x, int par){
	if(big[A[x]] >= 500)cur[A[x]]++;
	for(auto [i, j] : cur)fin[i][A[x]] += j;
	for(auto i : adj[x]){
		if(i == par)continue;
		dfs(i, x);
	}
	if(big[A[x]] >= 500)cur[A[x]]--;
}
int cnt = 1;
void dfs2(int x, int par){
	S[x] = cnt++;
	for(auto i : adj[x]){
		if(i == par)continue;
		dfs2(i, x);
	}
	E[x] = cnt - 1;
}

int find(int idx, int l, int r){
	return upper_bound(stuf2[idx].begin(), stuf2[idx].end(), r) - lower_bound(stuf2[idx].begin(), stuf2[idx].end(), l);
}

void solve(){
	cin >> n >> r >> q;
	cin >> A[1];
	for(int i=2;i<=n;i++){
		int x; cin >> x >> A[i];
		adj[x].push_back(i);
		big[A[i]]++;
	}
	if(1){
		dfs(1, -1);
		dfs2(1, -1);
		for(int i=1;i<=n;i++)stuf[A[i]].push_back(i), stuf2[A[i]].push_back(S[i]);
		for(int i=1;i<=r;i++)sort(stuf2[i].begin(), stuf2[i].end());
		int ans =0 ;
		while(q--){
			ans = 0;
			int x, y; cin >> x >> y;
			if(big[x] >= 500){
				cout << fin[x][y] << endl;
				continue;
			}
			for(auto i : stuf[x]){
				ans += find(y, S[i], E[i]);
			}
			cout << ans << endl;
		}
		return;
	}
	dfs(1, -1);
	while(q--){
		int x, y; cin >> x >> y;
		cout << fin[x][y] << endl;
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

regions.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main(){
      | ^~~~

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