Submission #660206

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
660206	2022-11-21T06:32:54 Z	QwertyPi	Regions (IOI09_regions)	C++14	90 / 100	8000 ms	126520 KB

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.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	12624 KB	Output is correct
2	Correct	7 ms	12632 KB	Output is correct
3	Correct	8 ms	12624 KB	Output is correct
4	Correct	11 ms	12688 KB	Output is correct
5	Correct	15 ms	12752 KB	Output is correct
6	Correct	25 ms	12796 KB	Output is correct
7	Correct	33 ms	12880 KB	Output is correct
8	Correct	30 ms	13008 KB	Output is correct
9	Correct	48 ms	13648 KB	Output is correct
10	Correct	93 ms	14416 KB	Output is correct
11	Correct	134 ms	15184 KB	Output is correct
12	Correct	147 ms	16372 KB	Output is correct
13	Correct	217 ms	16488 KB	Output is correct
14	Correct	289 ms	18388 KB	Output is correct
15	Correct	265 ms	21840 KB	Output is correct

Subtask #2

75.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	947 ms	26400 KB	Output is correct
2	Correct	1107 ms	26036 KB	Output is correct
3	Correct	1444 ms	30332 KB	Output is correct
4	Correct	327 ms	21144 KB	Output is correct
5	Correct	503 ms	21764 KB	Output is correct
6	Correct	663 ms	26456 KB	Output is correct
7	Correct	1210 ms	33004 KB	Output is correct
8	Correct	2078 ms	43136 KB	Output is correct
9	Correct	6302 ms	88236 KB	Output is correct
10	Correct	2951 ms	119436 KB	Output is correct
11	Correct	6896 ms	121144 KB	Output is correct
12	Execution timed out	8085 ms	62496 KB	Time limit exceeded
13	Correct	6542 ms	99896 KB	Output is correct
14	Execution timed out	8048 ms	103308 KB	Time limit exceeded
15	Correct	3864 ms	126520 KB	Output is correct
16	Correct	3634 ms	120324 KB	Output is correct
17	Correct	3441 ms	110020 KB	Output is correct