oj.uz

Submission #478216

# Submission time Handle Problem Language Result Execution time Memory
478216 2021-10-06T13:43:36 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
100 / 100
 4994 ms 34708 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
const int MX = 200005;
const int B = 447;
int N, R, Q;
vector <int> g[MX], region[MX];
int H[MX], st[MX], en[MX], stwho[MX];
int idx[MX], timer=1;
long long prep[B][25001];
	
void Flat(int v, int p) {
	stwho[timer] = v;
	st[v] = timer++;
	region[H[v]].push_back(st[v]);
	for(auto to : g[v]) if(to!=p) {
		Flat(to, v);
	}
	en[v] = timer-1;
}
void DFS(int v, int p, int reg, int cnt) {
	if(H[v]==reg) ++cnt;
	else prep[idx[reg]][H[v]] += cnt;
	for(auto u : g[v]) if(u!=p) {
		DFS(u, v, reg, cnt);
	}
}
int main() {
	cin >> N >> R >> Q;
	cin >> H[1];
	for(int i=2; i<=N; ++i) {
		int p; cin >> p >> H[i];
		g[p].push_back(i);
	}
	Flat(1, 1);
	int cur = 0;
	for(int i=1; i<=R; ++i) if(region[i].size()>B) {
		idx[i] = cur++;
		DFS(1, 1, i, 0);
	}
	// O(Q(rootNlogN + logR))
	while(Q--) {
		int r1, r2;
		cin >> r1 >> r2;
		long long ans = 0;
		if(region[r1].size()>B) {
			ans = prep[idx[r1]][r2];
		} else {
			for(auto p1 : region[r1]) {
				auto it = upper_bound(region[r2].begin(), region[r2].end(), en[stwho[p1]]);
				auto it2 = lower_bound(region[r2].begin(), region[r2].end(), p1);
				ans += it-it2; 
			}
		}
		assert(ans>=0);
		cout << ans << endl;
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9672 KB Output is correct
2 Correct 6 ms 9720 KB Output is correct
3 Correct 8 ms 9592 KB Output is correct
4 Correct 12 ms 9672 KB Output is correct
5 Correct 14 ms 9728 KB Output is correct
6 Correct 29 ms 9672 KB Output is correct
7 Correct 41 ms 9756 KB Output is correct
8 Correct 48 ms 9800 KB Output is correct
9 Correct 63 ms 10176 KB Output is correct
10 Correct 100 ms 10184 KB Output is correct
11 Correct 154 ms 10528 KB Output is correct
12 Correct 104 ms 10952 KB Output is correct
13 Correct 222 ms 10560 KB Output is correct
14 Correct 295 ms 11160 KB Output is correct
15 Correct 348 ms 13716 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2032 ms 14392 KB Output is correct
2 Correct 2524 ms 13120 KB Output is correct
3 Correct 3237 ms 16136 KB Output is correct
4 Correct 306 ms 11200 KB Output is correct
5 Correct 429 ms 12864 KB Output is correct
6 Correct 641 ms 15976 KB Output is correct
7 Correct 1860 ms 14632 KB Output is correct
8 Correct 1345 ms 26556 KB Output is correct
9 Correct 2393 ms 18404 KB Output is correct
10 Correct 3662 ms 34708 KB Output is correct
11 Correct 4994 ms 18112 KB Output is correct
12 Correct 1824 ms 20144 KB Output is correct
13 Correct 2368 ms 20300 KB Output is correct
14 Correct 2925 ms 23404 KB Output is correct
15 Correct 4038 ms 24424 KB Output is correct
16 Correct 3640 ms 29760 KB Output is correct
17 Correct 3252 ms 31900 KB Output is correct