oj.uz

Submission #660207

# Submission time Handle Problem Language Result Execution time Memory
660207 2022-11-21T06:46:06 Z QwertyPi Regions (IOI09_regions) C++14
90 / 100
 8000 ms 89792 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;

const int N = 1 << 18;
const int LGN = 18;
const int R = 1 << 15;
const int B = 150;
int p[N], r[N];
int tl[N], tr[N], preord[N], cnt[R];
int prec[N / B][R], id[R], ids = 0;
vector<int> G[N];
vector<int> emp[N];
vector<int> pos[R];
int n, rn, q;

int ct = 0;
void dfs(int v){
	tl[v] = ++ct; preord[ct] = v;
	for(auto u : G[v]){
		dfs(u);
	}
	tr[v] = ct;
}

void dfs_prec(int Co, int v, int acc = 0){
	for(auto u : G[v]){
		dfs_prec(Co, u, acc + (r[v] == Co));
	}
	prec[id[Co]][r[v]] += acc;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> rn >> q;
	cin >> r[1];
	for(int i = 2; i <= n; i++){
		cin >> p[i] >> r[i];
		G[p[i]].push_back(i);
		cnt[r[i]]++;
	}
	for(int i = 1; i <= n; i++){
		emp[r[i]].push_back(i);
	}
	dfs(1);
	for(int i = 1; i <= rn; i++){
		if(cnt[i] >= B){
			id[i] = ids;
			dfs_prec(i, 1);
			ids++;
		}
	}

	for(int i = 1; i <= n; i++){
		pos[r[preord[i]]].push_back(i);
	}
	
	for(int i = 0; i < q; i++){
		int r1, r2; cin >> r1 >> r2;
		if(cnt[r1] >= B){
			cout << prec[id[r1]][r2] << endl;
		}else{
			int ans = 0;
			for(auto i : emp[r1]){
				ans += upper_bound(pos[r2].begin(), pos[r2].end(), tr[i]) - lower_bound(pos[r2].begin(), pos[r2].end(), tl[i]);
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13392 KB Output is correct
2 Correct 6 ms 13392 KB Output is correct
3 Correct 9 ms 13392 KB Output is correct
4 Correct 11 ms 13392 KB Output is correct
5 Correct 14 ms 13432 KB Output is correct
6 Correct 19 ms 13520 KB Output is correct
7 Correct 32 ms 13520 KB Output is correct
8 Correct 32 ms 13520 KB Output is correct
9 Correct 59 ms 13904 KB Output is correct
10 Correct 87 ms 14032 KB Output is correct
11 Correct 114 ms 14288 KB Output is correct
12 Correct 128 ms 14800 KB Output is correct
13 Correct 115 ms 14680 KB Output is correct
14 Correct 292 ms 15588 KB Output is correct
15 Correct 192 ms 18236 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 19248 KB Output is correct
2 Correct 1151 ms 18204 KB Output is correct
3 Correct 1501 ms 21360 KB Output is correct
4 Correct 298 ms 16364 KB Output is correct
5 Correct 340 ms 16592 KB Output is correct
6 Correct 519 ms 18600 KB Output is correct
7 Correct 1057 ms 21328 KB Output is correct
8 Correct 1105 ms 26824 KB Output is correct
9 Correct 4433 ms 46924 KB Output is correct
10 Correct 2779 ms 88484 KB Output is correct
11 Correct 6679 ms 84744 KB Output is correct
12 Execution timed out 8026 ms 62384 KB Time limit exceeded
13 Correct 6633 ms 66736 KB Output is correct
14 Execution timed out 8021 ms 67644 KB Time limit exceeded
15 Correct 4099 ms 89792 KB Output is correct
16 Correct 3602 ms 83544 KB Output is correct
17 Correct 3335 ms 74364 KB Output is correct