Submission #660201

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
660201	2022-11-21T06:07:08 Z	QwertyPi	Regions (IOI09_regions)	C++14	85 / 100	8000 ms	121468 KB

regions

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

const int N = 2e5 + 11;
const int LGN = 20;
const int R = 2.5e4 + 11;
const int B = 200;
int p[N], r[N];
int tl[N], tr[N], preord[N], cnt[R];
int prec[N / B + 10][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 * 8] = {};
	int lch[N * LGN * 8] = {};
	int rch[N * LGN * 8] = {};
	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){
		if(l == r) return t[rt];
		int m = (l + r) / 2;
		if(qi <= m) return qry(qi, lch[rt], l, m);
		return qry(qi, rch[rt], m + 1, r);
	}
	
	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 = 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.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9724 KB	Output is correct
2	Correct	6 ms	9680 KB	Output is correct
3	Correct	6 ms	9680 KB	Output is correct
4	Correct	7 ms	9680 KB	Output is correct
5	Correct	12 ms	9784 KB	Output is correct
6	Correct	18 ms	9936 KB	Output is correct
7	Correct	29 ms	9936 KB	Output is correct
8	Correct	33 ms	10064 KB	Output is correct
9	Correct	46 ms	10832 KB	Output is correct
10	Correct	82 ms	11500 KB	Output is correct
11	Correct	128 ms	12356 KB	Output is correct
12	Correct	161 ms	13440 KB	Output is correct
13	Correct	224 ms	13680 KB	Output is correct
14	Correct	307 ms	14720 KB	Output is correct
15	Correct	427 ms	19016 KB	Output is correct

Subtask #2

70.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1476 ms	23652 KB	Output is correct
2	Correct	1196 ms	23300 KB	Output is correct
3	Correct	1597 ms	28612 KB	Output is correct
4	Correct	410 ms	16304 KB	Output is correct
5	Correct	462 ms	18828 KB	Output is correct
6	Correct	637 ms	23624 KB	Output is correct
7	Correct	1851 ms	29004 KB	Output is correct
8	Correct	2270 ms	42060 KB	Output is correct
9	Correct	5508 ms	53448 KB	Output is correct
10	Correct	7119 ms	95268 KB	Output is correct
11	Correct	7028 ms	116908 KB	Output is correct
12	Correct	7145 ms	76588 KB	Output is correct
13	Correct	7272 ms	77392 KB	Output is correct
14	Execution timed out	8013 ms	61256 KB	Time limit exceeded
15	Execution timed out	8035 ms	65144 KB	Time limit exceeded
16	Correct	3722 ms	121468 KB	Output is correct
17	Execution timed out	8048 ms	72260 KB	Time limit exceeded