Submission #660202

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
660202	2022-11-21T06:11:04 Z	QwertyPi	Regions (IOI09_regions)	C++14	75 / 100	8000 ms	122312 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 = 400;
int p[N], r[N];
int tl[N], tr[N], preord[N], cnt[R];
int prec[N / B + 10][R], id[R], ids = 0;
int prec2[R][N / B + 10], id2[R], ids2 = 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;
}

int dfs_prec2(int Co, int v){
	int acc = r[v] == Co;
	for(auto u : G[v]){
		acc += dfs_prec2(Co, u);
	}
	prec2[r[v]][id2[Co]] += acc;
	return 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++;
		}
	}

	for(int i = 1; i <= rn; i++){
		if(cnt[i] >= B){
			id2[i] = ids2;
			dfs_prec2(i, 1);
			ids2++;
		}
	}
	
	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 if(cnt[r2] >= B){
			cout << prec2[r1][id2[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	5 ms	9680 KB	Output is correct
2	Correct	5 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	8 ms	9740 KB	Output is correct
6	Correct	22 ms	9884 KB	Output is correct
7	Correct	28 ms	9936 KB	Output is correct
8	Correct	37 ms	10064 KB	Output is correct
9	Correct	46 ms	10832 KB	Output is correct
10	Correct	83 ms	11580 KB	Output is correct
11	Correct	138 ms	12368 KB	Output is correct
12	Correct	158 ms	13636 KB	Output is correct
13	Correct	222 ms	13592 KB	Output is correct
14	Correct	291 ms	14724 KB	Output is correct
15	Correct	398 ms	17872 KB	Output is correct

Subtask #2

60.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1730 ms	23652 KB	Output is correct
2	Correct	1846 ms	22940 KB	Output is correct
3	Correct	3857 ms	27844 KB	Output is correct
4	Correct	424 ms	16232 KB	Output is correct
5	Correct	538 ms	18768 KB	Output is correct
6	Correct	725 ms	37440 KB	Output is correct
7	Correct	2672 ms	47568 KB	Output is correct
8	Correct	2001 ms	62024 KB	Output is correct
9	Execution timed out	8035 ms	46536 KB	Time limit exceeded
10	Correct	6783 ms	118396 KB	Output is correct
11	Execution timed out	8006 ms	57864 KB	Time limit exceeded
12	Correct	4917 ms	87656 KB	Output is correct
13	Correct	7169 ms	88136 KB	Output is correct
14	Correct	6912 ms	99796 KB	Output is correct
15	Execution timed out	8032 ms	115064 KB	Time limit exceeded
16	Execution timed out	8036 ms	122312 KB	Time limit exceeded
17	Execution timed out	8080 ms	110800 KB	Time limit exceeded