oj.uz

Submission #1065059

# Submission time Handle Problem Language Result Execution time Memory
1065059 2024-08-18T21:53:41 Z belgianbot Regions (IOI09_regions) C++17
100 / 100
 3118 ms 45828 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int cnt = 0, N, SQRT, R;

vector<int> a, in, out, occ;
vector<vector<int>> child;
map<int, vector<ll>> col;
map<int,int> curr;
vector<vector<pair<int,int>>> pref;

void dfs(int x) {
	int last = 0;
	if (!pref[a[x]].empty()) last = pref[a[x]].back().second;
	pref[a[x]].push_back({cnt, last + 1});
	in[x] = cnt++;
	
	if (occ[a[x]] > SQRT) curr[a[x]]++;
	for (int y : child[x]) {
		dfs(y);
	}
	if (occ[a[x]] > SQRT) curr[a[x]] --;
	for (auto z : curr) col[z.first][a[x]] += z.second;
	out[x] = cnt;
	
}

signed main() {
	ios::sync_with_stdio(false);
	int Q; cin >> N >> R >> Q;
	a.resize(N); child.resize(N); in.resize(N); out.resize(N); cin >> a[0]; a[0]--;
	occ.resize(R, 0); occ[a[0]]++; pref.resize(R);
	for (int i = 1; i < N; i++) {
		int b; cin >> b >> a[i]; b--; a[i]--; occ[a[i]]++;
		child[b].push_back(i);
	}
	SQRT=sqrt(N);
	vector<vector<int>> temp(R);
	for (int i = 0; i < N; i++) {
		if (occ[a[i]] <= SQRT) temp[a[i]].push_back(i);

	}
	for (int i = 0; i < R; i++) {
		if (occ[i] > SQRT) col[i].resize(R);
	}
	dfs(0);
	
	while (Q--) {
		int r1, r2; cin >> r1 >> r2; r1--; r2--;
		if (occ[r1] > SQRT) cout << col[r1][r2] << '\n';
		
		else {
			ll ans = 0;
			for (int x : temp[r1]) {
				auto it = upper_bound(pref[r2].begin(), pref[r2].end(), make_pair(out[x], -1)); 
				if (it == pref[r2].begin()) continue;
				it--;
				if ((*it).first < in[x]) continue;
				int last = 0;
				auto it2 = upper_bound(pref[r2].begin(), pref[r2].end(), make_pair(in[x], -1));
				if (it2 != pref[r2].begin()) {
					it2--;
					last = (*it2).second;
				}
				ans += (*it).second - last;
			}
			cout << ans << '\n';
		}
	}
		
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 11 ms 600 KB Output is correct
7 Correct 14 ms 600 KB Output is correct
8 Correct 12 ms 600 KB Output is correct
9 Correct 24 ms 1368 KB Output is correct
10 Correct 43 ms 1112 KB Output is correct
11 Correct 84 ms 1624 KB Output is correct
12 Correct 104 ms 2648 KB Output is correct
13 Correct 120 ms 2136 KB Output is correct
14 Correct 195 ms 3032 KB Output is correct
15 Correct 218 ms 8524 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1467 ms 8052 KB Output is correct
2 Correct 1549 ms 6236 KB Output is correct
3 Correct 2459 ms 11544 KB Output is correct
4 Correct 192 ms 3348 KB Output is correct
5 Correct 265 ms 6644 KB Output is correct
6 Correct 401 ms 8712 KB Output is correct
7 Correct 838 ms 11112 KB Output is correct
8 Correct 911 ms 24608 KB Output is correct
9 Correct 1920 ms 16296 KB Output is correct
10 Correct 2533 ms 45828 KB Output is correct
11 Correct 3118 ms 16892 KB Output is correct
12 Correct 1087 ms 17620 KB Output is correct
13 Correct 1523 ms 18804 KB Output is correct
14 Correct 1725 ms 21512 KB Output is correct
15 Correct 2619 ms 26824 KB Output is correct
16 Correct 2543 ms 39616 KB Output is correct
17 Correct 2384 ms 40048 KB Output is correct