Submission #440155

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
440155	2021-07-01T16:29:16 Z	dutch	Regions (IOI09_regions)	C++17	100 / 100	5161 ms	35056 KB

regions

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 2e5, MAXK = 2.5e4, SQRT = 350;
 
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	10 ms	10824 KB	Output is correct
2	Correct	8 ms	10776 KB	Output is correct
3	Correct	10 ms	10824 KB	Output is correct
4	Correct	12 ms	10824 KB	Output is correct
5	Correct	18 ms	10824 KB	Output is correct
6	Correct	36 ms	10936 KB	Output is correct
7	Correct	37 ms	10952 KB	Output is correct
8	Correct	42 ms	10952 KB	Output is correct
9	Correct	77 ms	11336 KB	Output is correct
10	Correct	129 ms	11336 KB	Output is correct
11	Correct	187 ms	11720 KB	Output is correct
12	Correct	177 ms	12232 KB	Output is correct
13	Correct	168 ms	11900 KB	Output is correct
14	Correct	320 ms	12488 KB	Output is correct
15	Correct	315 ms	15048 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2278 ms	15512 KB	Output is correct
2	Correct	2707 ms	14360 KB	Output is correct
3	Correct	3369 ms	17344 KB	Output is correct
4	Correct	327 ms	12488 KB	Output is correct
5	Correct	319 ms	14188 KB	Output is correct
6	Correct	744 ms	15432 KB	Output is correct
7	Correct	1536 ms	16228 KB	Output is correct
8	Correct	1266 ms	23752 KB	Output is correct
9	Correct	2729 ms	20288 KB	Output is correct
10	Correct	3402 ms	35056 KB	Output is correct
11	Correct	5161 ms	20176 KB	Output is correct
12	Correct	1699 ms	21668 KB	Output is correct
13	Correct	2428 ms	21868 KB	Output is correct
14	Correct	3406 ms	23320 KB	Output is correct
15	Correct	3621 ms	26084 KB	Output is correct
16	Correct	3571 ms	31472 KB	Output is correct
17	Correct	3226 ms	31936 KB	Output is correct