Submission #440166

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
440166	2021-07-01T16:43:15 Z	dutch	Regions (IOI09_regions)	C++17	100 / 100	5231 ms	31868 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 bs(vector<int> &v, int val){
	int x = -1;
	for(int y=1<<15; y/=2; ) if(x+y < (int)v.size() && v[x+y] <= val) x += y;
	return x;
}
 
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 += bs(ord[y], t[u]+s[u]-1) - bs(ord[y], t[u]-1);
			}
			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	10844 KB	Output is correct
2	Correct	9 ms	10824 KB	Output is correct
3	Correct	8 ms	10856 KB	Output is correct
4	Correct	17 ms	10824 KB	Output is correct
5	Correct	17 ms	10824 KB	Output is correct
6	Correct	22 ms	10952 KB	Output is correct
7	Correct	41 ms	11080 KB	Output is correct
8	Correct	43 ms	10952 KB	Output is correct
9	Correct	60 ms	11336 KB	Output is correct
10	Correct	135 ms	11336 KB	Output is correct
11	Correct	149 ms	11720 KB	Output is correct
12	Correct	157 ms	12180 KB	Output is correct
13	Correct	226 ms	11872 KB	Output is correct
14	Correct	232 ms	12432 KB	Output is correct
15	Correct	333 ms	15048 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1676 ms	15508 KB	Output is correct
2	Correct	2050 ms	14356 KB	Output is correct
3	Correct	2987 ms	17288 KB	Output is correct
4	Correct	370 ms	12464 KB	Output is correct
5	Correct	461 ms	14152 KB	Output is correct
6	Correct	786 ms	15552 KB	Output is correct
7	Correct	1544 ms	15400 KB	Output is correct
8	Correct	1260 ms	23756 KB	Output is correct
9	Correct	2975 ms	20232 KB	Output is correct
10	Correct	4561 ms	30556 KB	Output is correct
11	Correct	5231 ms	20172 KB	Output is correct
12	Correct	1669 ms	21672 KB	Output is correct
13	Correct	2186 ms	21860 KB	Output is correct
14	Correct	3211 ms	23336 KB	Output is correct
15	Correct	3638 ms	26080 KB	Output is correct
16	Correct	4477 ms	31460 KB	Output is correct
17	Correct	4226 ms	31868 KB	Output is correct