Submission #440150

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
440150	2021-07-01T16:25:10 Z	dutch	Regions (IOI09_regions)	C++17	75 / 100	8000 ms	84864 KB

regions

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

const int MAXN = 2e5, MAXK = 2.5e4, SQRT = 150;

int k[MAXN], cnt[MAXK], t[MAXN], s[MAXN], dfsTimer = 0, cur, c;
vector<int> g[MAXN], a[MAXN], res[MAXK], ord[MAXK];

void dfs0(int u){
	t[u] = dfsTimer++, s[u] = 1;
	ord[k[u]].push_back(t[u]);
	for(int v : g[u]) dfs0(v), s[u] += s[v];
}

void dfs1(int u){
	if(k[u] == cur) ++c;
	res[cur][k[u]] += c;
	for(int v : g[u]) dfs1(v);
	if(k[u] == cur) --c;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n, r, q, x, y; cin >> n >> r >> q;

	for(int i=0, j; i<n; ++i){
		if(i) cin >> j, g[j-1].push_back(i);
		cin >> k[i], a[--k[i]].push_back(i);
	}

	dfs0(0);

	for(int i=0; i<r; ++i){
		if(a[i].size() < SQRT) continue;
		cur = i, c = 0;
		res[i].resize(r);
		dfs1(0);
	}

	while(q--){
		cin >> x >> y; --x, --y;
		if(a[x].size() < SQRT){
			int ans = 0;
			for(int u : a[x]){
				ans += upper_bound(ord[y].begin(), ord[y].end(), t[u]+s[u]-1)
					 - lower_bound(ord[y].begin(), ord[y].end(), t[u]);
			}
			cout << ans << endl;
		}else{
			cout << res[x][y] << endl;
		}
	}
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	10824 KB	Output is correct
2	Correct	8 ms	10824 KB	Output is correct
3	Correct	10 ms	10824 KB	Output is correct
4	Correct	11 ms	10824 KB	Output is correct
5	Correct	21 ms	10824 KB	Output is correct
6	Correct	18 ms	10952 KB	Output is correct
7	Correct	21 ms	10952 KB	Output is correct
8	Correct	52 ms	11020 KB	Output is correct
9	Correct	65 ms	11336 KB	Output is correct
10	Correct	128 ms	11372 KB	Output is correct
11	Correct	151 ms	11648 KB	Output is correct
12	Correct	184 ms	12100 KB	Output is correct
13	Correct	300 ms	11908 KB	Output is correct
14	Correct	411 ms	12544 KB	Output is correct
15	Correct	491 ms	15220 KB	Output is correct

Subtask #2

60.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1476 ms	15736 KB	Output is correct
2	Correct	1668 ms	14564 KB	Output is correct
3	Correct	1957 ms	17556 KB	Output is correct
4	Correct	318 ms	13372 KB	Output is correct
5	Correct	456 ms	14208 KB	Output is correct
6	Correct	876 ms	15428 KB	Output is correct
7	Correct	1316 ms	17868 KB	Output is correct
8	Correct	1663 ms	23752 KB	Output is correct
9	Correct	6905 ms	41420 KB	Output is correct
10	Correct	4364 ms	83992 KB	Output is correct
11	Execution timed out	8090 ms	75744 KB	Time limit exceeded
12	Execution timed out	8019 ms	42032 KB	Time limit exceeded
13	Execution timed out	8076 ms	54132 KB	Time limit exceeded
14	Execution timed out	8058 ms	52468 KB	Time limit exceeded
15	Execution timed out	8045 ms	84864 KB	Time limit exceeded
16	Correct	4644 ms	80404 KB	Output is correct
17	Correct	4918 ms	71100 KB	Output is correct