Submission #660211

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
660211	2022-11-21T06:55:51 Z	QwertyPi	Regions (IOI09_regions)	C++14	100 / 100	5345 ms	34088 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 = 25001;
const int B = 500;
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;
}

bool vis[N];
void dfs_prec(int Co, int v, int acc = 0){
	if(r[v] == Co) vis[v] = true;
	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;
			ids++;
		}
	}

	for(int i = 1; i <= n; i++){
		if(cnt[r[i]] >= B && !vis[i]){
			dfs_prec(r[i], i);
		}
	}

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	13224 KB	Output is correct
2	Correct	8 ms	13136 KB	Output is correct
3	Correct	10 ms	13136 KB	Output is correct
4	Correct	12 ms	13136 KB	Output is correct
5	Correct	15 ms	13264 KB	Output is correct
6	Correct	21 ms	13264 KB	Output is correct
7	Correct	22 ms	13264 KB	Output is correct
8	Correct	43 ms	13392 KB	Output is correct
9	Correct	61 ms	13648 KB	Output is correct
10	Correct	93 ms	13776 KB	Output is correct
11	Correct	134 ms	14088 KB	Output is correct
12	Correct	167 ms	14652 KB	Output is correct
13	Correct	201 ms	14356 KB	Output is correct
14	Correct	309 ms	15008 KB	Output is correct
15	Correct	296 ms	16976 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1783 ms	18420 KB	Output is correct
2	Correct	2431 ms	17460 KB	Output is correct
3	Correct	2959 ms	20116 KB	Output is correct
4	Correct	252 ms	15056 KB	Output is correct
5	Correct	383 ms	16280 KB	Output is correct
6	Correct	1162 ms	17172 KB	Output is correct
7	Correct	2031 ms	17620 KB	Output is correct
8	Correct	1493 ms	22316 KB	Output is correct
9	Correct	2487 ms	23508 KB	Output is correct
10	Correct	4438 ms	27472 KB	Output is correct
11	Correct	5345 ms	24164 KB	Output is correct
12	Correct	1770 ms	25712 KB	Output is correct
13	Correct	2333 ms	25724 KB	Output is correct
14	Correct	2796 ms	27572 KB	Output is correct
15	Correct	3268 ms	29564 KB	Output is correct
16	Correct	2907 ms	33288 KB	Output is correct
17	Correct	2777 ms	34088 KB	Output is correct