oj.uz

Submission #956505

# Submission time Handle Problem Language Result Execution time Memory
956505 2024-04-02T06:14:06 Z Trisanu_Das Regions (IOI09_regions) C++17
100 / 100
 3458 ms 35528 KB 
#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 3 ms 12888 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct
4 Correct 5 ms 12888 KB Output is correct
5 Correct 7 ms 12888 KB Output is correct
6 Correct 13 ms 12888 KB Output is correct
7 Correct 22 ms 12888 KB Output is correct
8 Correct 21 ms 12888 KB Output is correct
9 Correct 27 ms 13400 KB Output is correct
10 Correct 47 ms 13400 KB Output is correct
11 Correct 78 ms 13520 KB Output is correct
12 Correct 84 ms 13912 KB Output is correct
13 Correct 107 ms 13656 KB Output is correct
14 Correct 204 ms 14108 KB Output is correct
15 Correct 214 ms 16628 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1403 ms 16724 KB Output is correct
2 Correct 1698 ms 15528 KB Output is correct
3 Correct 2285 ms 18316 KB Output is correct
4 Correct 175 ms 14168 KB Output is correct
5 Correct 246 ms 15600 KB Output is correct
6 Correct 380 ms 16880 KB Output is correct
7 Correct 937 ms 17516 KB Output is correct
8 Correct 775 ms 24880 KB Output is correct
9 Correct 1793 ms 20900 KB Output is correct
10 Correct 2285 ms 35528 KB Output is correct
11 Correct 3458 ms 20408 KB Output is correct
12 Correct 1085 ms 21976 KB Output is correct
13 Correct 1486 ms 22420 KB Output is correct
14 Correct 1690 ms 23572 KB Output is correct
15 Correct 2505 ms 26324 KB Output is correct
16 Correct 2354 ms 31704 KB Output is correct
17 Correct 2213 ms 32236 KB Output is correct