Submission #440158

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
440158	2021-07-01T16:31:08 Z	dutch	Regions (IOI09_regions)	C++17	100 / 100	5576 ms	31864 KB

regions

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 2e5, MAXK = 2.5e4, SQRT = 450;
 
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	8 ms	10824 KB	Output is correct
2	Correct	9 ms	10824 KB	Output is correct
3	Correct	10 ms	10824 KB	Output is correct
4	Correct	14 ms	10824 KB	Output is correct
5	Correct	17 ms	10824 KB	Output is correct
6	Correct	30 ms	10936 KB	Output is correct
7	Correct	35 ms	10956 KB	Output is correct
8	Correct	45 ms	11008 KB	Output is correct
9	Correct	56 ms	11336 KB	Output is correct
10	Correct	101 ms	11336 KB	Output is correct
11	Correct	139 ms	11624 KB	Output is correct
12	Correct	222 ms	12232 KB	Output is correct
13	Correct	241 ms	11848 KB	Output is correct
14	Correct	402 ms	12464 KB	Output is correct
15	Correct	383 ms	15048 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2542 ms	15512 KB	Output is correct
2	Correct	2764 ms	14364 KB	Output is correct
3	Correct	3666 ms	17216 KB	Output is correct
4	Correct	407 ms	12488 KB	Output is correct
5	Correct	405 ms	14176 KB	Output is correct
6	Correct	591 ms	15436 KB	Output is correct
7	Correct	2131 ms	15392 KB	Output is correct
8	Correct	1537 ms	23756 KB	Output is correct
9	Correct	3175 ms	20292 KB	Output is correct
10	Correct	4715 ms	30552 KB	Output is correct
11	Correct	5576 ms	20176 KB	Output is correct
12	Correct	1738 ms	21672 KB	Output is correct
13	Correct	2762 ms	21868 KB	Output is correct
14	Correct	3320 ms	23320 KB	Output is correct
15	Correct	3981 ms	26080 KB	Output is correct
16	Correct	4091 ms	31464 KB	Output is correct
17	Correct	3759 ms	31864 KB	Output is correct