Submission #660207

#	Time	Username	Problem	Language	Result	Execution time	Memory
660207		QwertyPi	Regions (IOI09_regions)	C++14	90 / 100	8026 ms	89792 KiB

regions

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;

const int N = 1 << 18;
const int LGN = 18;
const int R = 1 << 15;
const int B = 150;
int p[N], r[N];
int tl[N], tr[N], preord[N], cnt[R];
int prec[N / B][R], id[R], ids = 0;
vector<int> G[N];
vector<int> emp[N];
vector<int> pos[R];
int n, rn, q;

int ct = 0;
void dfs(int v){
	tl[v] = ++ct; preord[ct] = v;
	for(auto u : G[v]){
		dfs(u);
	}
	tr[v] = ct;
}

void dfs_prec(int Co, int v, int acc = 0){
	for(auto u : G[v]){
		dfs_prec(Co, u, acc + (r[v] == Co));
	}
	prec[id[Co]][r[v]] += acc;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> rn >> q;
	cin >> r[1];
	for(int i = 2; i <= n; i++){
		cin >> p[i] >> r[i];
		G[p[i]].push_back(i);
		cnt[r[i]]++;
	}
	for(int i = 1; i <= n; i++){
		emp[r[i]].push_back(i);
	}
	dfs(1);
	for(int i = 1; i <= rn; i++){
		if(cnt[i] >= B){
			id[i] = ids;
			dfs_prec(i, 1);
			ids++;
		}
	}

	for(int i = 1; i <= n; i++){
		pos[r[preord[i]]].push_back(i);
	}
	
	for(int i = 0; i < q; i++){
		int r1, r2; cin >> r1 >> r2;
		if(cnt[r1] >= B){
			cout << prec[id[r1]][r2] << endl;
		}else{
			int ans = 0;
			for(auto i : emp[r1]){
				ans += upper_bound(pos[r2].begin(), pos[r2].end(), tr[i]) - lower_bound(pos[r2].begin(), pos[r2].end(), tl[i]);
			}
			cout << ans << endl;
		}
	}
	return 0;
}

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