oj.uz

Submission #534325

# Submission time Handle Problem Language Result Execution time Memory
534325 2022-03-08T04:41:56 Z Cantfindme Regions (IOI09_regions) C++17
100 / 100
 4885 ms 45728 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

const int maxn = 200010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;
const int len = 450;

int n, R, Q;
vector <int> adjlist[maxn];
vector <int> v[maxn], v2[maxn];
int ans[len+10][maxn];
int indx[maxn], rev[maxn], col[maxn];

int pre[maxn], post[maxn];

int co = 1;
void dfs(int x, int p) {
	pre[x] = co++;
	rev[pre[x]] = x;
	for (auto i: adjlist[x]) if (i != p) {
		dfs(i,x);
	}
	post[x] = co - 1;

}

int32_t main() {
	// ifstream cin("input.txt");

	cin >> n >> R >> Q;
	for (int i =1;i<=n;i++) {
		if (i == 1) {
			int x; cin >> x;
			col[i] = x;
			v[x].push_back(i);
		} else {
			int x, p; cin >> p >> x;
			col[i] = x;
			v[x].push_back(i);
			adjlist[p].push_back(i);
		}
	}
	dfs(1,-1);

	co = 0;
	for (int x = 1; x <= R; x++) {
		for (auto i: v[x]) {
			v2[x].push_back(pre[i]);
		}
		sort(all(v2[x]));

		if (v[x].size() >= len) {
			indx[x] = co; 
			vector <int> pref(n+2, 0);
			for (auto i: v[x]) {
				pref[pre[i]]++;
				pref[post[i]+1]--;
			}

			int cur = 0;
			for (int j = 1; j<= n;j++) {
				cur += pref[j];
				int child = rev[j];
				ans[indx[x]][col[child]] += cur;
			}

			co++;
		}
	}

	for (int q=0;q<Q;q++) {
		int r1, r2; cin >> r1 >> r2;
		if (v[r1].size() >= len) {
			cout << ans[indx[r1]][r2] << "\n";
		} else {
			int rans = 0;
			for (auto i: v[r1]) { //sqrt(N)
				int lb = lower_bound(all(v2[r2]), pre[i]) - v2[r2].begin();
				int rb = upper_bound(all(v2[r2]), post[i]) - v2[r2].begin();
				rans += rb - lb;
			}
			cout << rans << "\n";
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14408 KB Output is correct
2 Correct 11 ms 14408 KB Output is correct
3 Correct 11 ms 14408 KB Output is correct
4 Correct 12 ms 14408 KB Output is correct
5 Correct 16 ms 14408 KB Output is correct
6 Correct 30 ms 14408 KB Output is correct
7 Correct 35 ms 14536 KB Output is correct
8 Correct 48 ms 14580 KB Output is correct
9 Correct 65 ms 15048 KB Output is correct
10 Correct 86 ms 15148 KB Output is correct
11 Correct 103 ms 15560 KB Output is correct
12 Correct 162 ms 16328 KB Output is correct
13 Correct 226 ms 16200 KB Output is correct
14 Correct 343 ms 16872 KB Output is correct
15 Correct 289 ms 19664 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2009 ms 22044 KB Output is correct
2 Correct 2358 ms 21148 KB Output is correct
3 Correct 3239 ms 24164 KB Output is correct
4 Correct 272 ms 16960 KB Output is correct
5 Correct 415 ms 18624 KB Output is correct
6 Correct 554 ms 22928 KB Output is correct
7 Correct 1629 ms 22088 KB Output is correct
8 Correct 1252 ms 35424 KB Output is correct
9 Correct 2650 ms 28432 KB Output is correct
10 Correct 3820 ms 45728 KB Output is correct
11 Correct 4885 ms 29664 KB Output is correct
12 Correct 1640 ms 31432 KB Output is correct
13 Correct 2128 ms 31684 KB Output is correct
14 Correct 2487 ms 36128 KB Output is correct
15 Correct 3253 ms 36784 KB Output is correct
16 Correct 2974 ms 41876 KB Output is correct
17 Correct 3208 ms 44592 KB Output is correct