Submission #1065059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065059		belgianbot	Regions (IOI09_regions)	C++17	100 / 100	3118 ms	45828 KiB

regions

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int cnt = 0, N, SQRT, R;

vector<int> a, in, out, occ;
vector<vector<int>> child;
map<int, vector<ll>> col;
map<int,int> curr;
vector<vector<pair<int,int>>> pref;

void dfs(int x) {
	int last = 0;
	if (!pref[a[x]].empty()) last = pref[a[x]].back().second;
	pref[a[x]].push_back({cnt, last + 1});
	in[x] = cnt++;
	
	if (occ[a[x]] > SQRT) curr[a[x]]++;
	for (int y : child[x]) {
		dfs(y);
	}
	if (occ[a[x]] > SQRT) curr[a[x]] --;
	for (auto z : curr) col[z.first][a[x]] += z.second;
	out[x] = cnt;
	
}

signed main() {
	ios::sync_with_stdio(false);
	int Q; cin >> N >> R >> Q;
	a.resize(N); child.resize(N); in.resize(N); out.resize(N); cin >> a[0]; a[0]--;
	occ.resize(R, 0); occ[a[0]]++; pref.resize(R);
	for (int i = 1; i < N; i++) {
		int b; cin >> b >> a[i]; b--; a[i]--; occ[a[i]]++;
		child[b].push_back(i);
	}
	SQRT=sqrt(N);
	vector<vector<int>> temp(R);
	for (int i = 0; i < N; i++) {
		if (occ[a[i]] <= SQRT) temp[a[i]].push_back(i);

	}
	for (int i = 0; i < R; i++) {
		if (occ[i] > SQRT) col[i].resize(R);
	}
	dfs(0);
	
	while (Q--) {
		int r1, r2; cin >> r1 >> r2; r1--; r2--;
		if (occ[r1] > SQRT) cout << col[r1][r2] << '\n';
		
		else {
			ll ans = 0;
			for (int x : temp[r1]) {
				auto it = upper_bound(pref[r2].begin(), pref[r2].end(), make_pair(out[x], -1)); 
				if (it == pref[r2].begin()) continue;
				it--;
				if ((*it).first < in[x]) continue;
				int last = 0;
				auto it2 = upper_bound(pref[r2].begin(), pref[r2].end(), make_pair(in[x], -1));
				if (it2 != pref[r2].begin()) {
					it2--;
					last = (*it2).second;
				}
				ans += (*it).second - last;
			}
			cout << ans << '\n';
		}
	}
		
	return 0;
}
		
	
	
	

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