oj.uz

Submission #440147

# Submission time Handle Problem Language Result Execution time Memory
440147 2021-07-01T16:22:18 Z dutch Regions (IOI09_regions) C++17
18 / 100
 429 ms 64824 KB 
#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) ++cur;
	res[cur][k[u]] += c;
	for(int v : g[u]) dfs1(v);
	if(k[u] == cur) --cur;
}

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(n);
		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
13.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 11 ms 10824 KB Output is correct
4 Correct 12 ms 10824 KB Output is correct
5 Correct 21 ms 10824 KB Output is correct
6 Correct 36 ms 10952 KB Output is correct
7 Correct 53 ms 10952 KB Output is correct
8 Correct 49 ms 10952 KB Output is correct
9 Correct 71 ms 11336 KB Output is correct
10 Correct 87 ms 11336 KB Output is correct
11 Correct 146 ms 11624 KB Output is correct
12 Correct 222 ms 12104 KB Output is correct
13 Correct 248 ms 11976 KB Output is correct
14 Runtime error 33 ms 25416 KB Execution killed with signal 11
15 Runtime error 40 ms 30564 KB Execution killed with signal 11

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 31796 KB Execution killed with signal 11
2 Runtime error 54 ms 29512 KB Execution killed with signal 11
3 Runtime error 58 ms 35568 KB Execution killed with signal 11
4 Runtime error 73 ms 25536 KB Execution killed with signal 11
5 Correct 429 ms 14152 KB Output is correct
6 Runtime error 47 ms 28228 KB Execution killed with signal 11
7 Runtime error 57 ms 30400 KB Execution killed with signal 11
8 Runtime error 71 ms 40756 KB Execution killed with signal 11
9 Runtime error 102 ms 42200 KB Execution killed with signal 11
10 Runtime error 106 ms 52364 KB Execution killed with signal 11
11 Runtime error 121 ms 42304 KB Execution killed with signal 11
12 Runtime error 160 ms 44984 KB Execution killed with signal 11
13 Runtime error 136 ms 45360 KB Execution killed with signal 11
14 Runtime error 155 ms 45164 KB Execution killed with signal 11
15 Runtime error 127 ms 53972 KB Execution killed with signal 11
16 Runtime error 142 ms 64824 KB Execution killed with signal 11
17 Runtime error 131 ms 62400 KB Execution killed with signal 11