제출 #660206

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660206		QwertyPi	Regions (IOI09_regions)	C++14	90 / 100	8085 ms	126520 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 = 128;
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];
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;
}

namespace DS{
	int a[N] = {}, roots[N];
	int t[N * LGN * 4] = {};
	int lch[N * LGN * 4] = {};
	int rch[N * LGN * 4] = {};
	int cc = 0;
	
	int build(int rt, int l, int r){
		if(l == r) return rt;
		int m = (l + r) / 2;
		int lc = build(++cc, l, m);
		int rc = build(++cc, m + 1, r);
		lch[rt] = lc, rch[rt] = rc;
		return rt;
	}

	int add(int qi, int qv, int rt, int l, int r){
		if(l == r) { t[++cc] = t[rt] + qv; return cc; }
		int m = (l + r) / 2;
		if(qi <= m){
			int lc = add(qi, qv, lch[rt], l, m);
			int rc = rch[rt];
			lch[++cc] = lc, rch[cc] = rc;
		}else{
			int lc = lch[rt];
			int rc = add(qi, qv, rch[rt], m + 1, r);
			lch[++cc] = lc, rch[cc] = rc;
		}
		return cc;
	}

	int qry(int qi, int rt, int l, int r){
		while(l != r){
			int m = (l + r) / 2;
			if(qi <= m) rt = lch[rt], r = m;
			else rt = rch[rt], l = m + 1;
		}
		return t[rt];
	}
	
	void init(int n){
		for(int i = 1; i <= n; i++){
			a[i] = r[preord[i]];
		}
		roots[0] = build(0, 1, rn);
		for(int i = 1; i <= n; i++){
			roots[i] = add(a[i], 1, roots[i - 1], 1, rn);
		}
	}
};

int qry(int _l, int _r, int v){
	return DS::qry(v, DS::roots[_r], 1, rn) - DS::qry(v, DS::roots[_l - 1], 1, rn);
}

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++;
		}
	}

	DS::init(n);
	for(int i = 1; i <= n; i++){
		G[i].clear();
	}
	
	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 += qry(tl[i], tr[i], r2);
			}
			cout << ans << endl;
		}
	}
	return 0;
}

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