oj.uz

Submission #1050152

# Submission time Handle Problem Language Result Execution time Memory
1050152 2024-08-09T07:45:02 Z BuzzyBeez Regions (IOI09_regions) C++17
100 / 100
 1905 ms 82556 KB 
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("arch=skylake")
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[200008];
int color[200008];
vector<int> occ[25008], occ2[25008];
int tin[200008], tout[200008], euler[200008];
vector<int> ans[25008]; int hrank[25008];
int upd[200008], dp[200008];

void add_edge(int u, int v) {adj[u].push_back(v); adj[v].push_back(u);}

int timer = 0;
void DFS_EulerTour(int u) {
	tin[u] = ++timer; euler[timer] = u;
	for (int v : adj[u]) DFS_EulerTour(v);
	tout[u] = timer;
}

int get(int c, int l, int r) {
	if (l > r) return 0;
	return upper_bound(occ2[c].begin(), occ2[c].end(), r) - lower_bound(occ2[c].begin(), occ2[c].end(), l);
}

signed main() {
	int n, R, q, u, v, r1, r2, res; cin >> n >> R >> q >> color[1];
	for (u = 2; u <= n; ++u) cin >> v >> color[u], adj[v].push_back(u);
	DFS_EulerTour(1);
	// for (int i = 1; i <= n; ++i) cout << tin[i] << ' ' << tout[i] << '\n';
	for (u = 1; u <= n; ++u) occ[color[u]].push_back(u);
	int S = sqrt(3.0 * n * R / (q * (__lg(n) + 1)));
	vector<int> heavy;
	for (int c = 1; c <= R; ++c) if (occ[c].size() > S) heavy.push_back(c), hrank[c] = heavy.size();
	for (int c = 1; c <= R; ++c) ans[c].resize(heavy.size() + 1);
	for (int c : heavy) {
		for (int u : occ[c]) ++upd[tin[u] + 1], --upd[tout[u] + 1];
		for (int i = 1; i <= n; ++i) dp[i] = dp[i - 1] + upd[i];
		for (int i = 1; i <= n; ++i) ans[color[euler[i]]][hrank[c]] += dp[i];
		for (int i = 1; i <= n; ++i) dp[i] = 0, upd[i] = 0;
	}
	for (int c = 1; c <= R; ++c) {
		for (int u : occ[c]) occ2[c].push_back(tin[u]);
		sort(occ2[c].begin(), occ2[c].end());
	}
	while (q--) {
		cin >> r1 >> r2; 
		if (occ[r1].size() > S) cout << ans[r2][hrank[r1]] << endl;
		else {
			res = 0;
			for (int u : occ[r1]) res += get(r2, tin[u] + 1, tout[u]);
			cout << res << endl;
		}
	}
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:35:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |  for (int c = 1; c <= R; ++c) if (occ[c].size() > S) heavy.push_back(c), hrank[c] = heavy.size();
      |                                   ~~~~~~~~~~~~~~^~~
regions.cpp:49:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |   if (occ[r1].size() > S) cout << ans[r2][hrank[r1]] << endl;
      |       ~~~~~~~~~~~~~~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is correct
2 Correct 2 ms 11352 KB Output is correct
3 Correct 3 ms 11352 KB Output is correct
4 Correct 4 ms 11352 KB Output is correct
5 Correct 5 ms 11496 KB Output is correct
6 Correct 11 ms 11608 KB Output is correct
7 Correct 13 ms 11608 KB Output is correct
8 Correct 16 ms 11608 KB Output is correct
9 Correct 26 ms 12120 KB Output is correct
10 Correct 46 ms 12632 KB Output is correct
11 Correct 64 ms 12376 KB Output is correct
12 Correct 95 ms 13144 KB Output is correct
13 Correct 96 ms 12632 KB Output is correct
14 Correct 113 ms 12828 KB Output is correct
15 Correct 131 ms 14612 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 15332 KB Output is correct
2 Correct 534 ms 14180 KB Output is correct
3 Correct 723 ms 16500 KB Output is correct
4 Correct 158 ms 14344 KB Output is correct
5 Correct 239 ms 21700 KB Output is correct
6 Correct 327 ms 15416 KB Output is correct
7 Correct 543 ms 19608 KB Output is correct
8 Correct 667 ms 34060 KB Output is correct
9 Correct 1404 ms 54220 KB Output is correct
10 Correct 1583 ms 81488 KB Output is correct
11 Correct 1901 ms 77312 KB Output is correct
12 Correct 1396 ms 57948 KB Output is correct
13 Correct 1447 ms 57880 KB Output is correct
14 Correct 1658 ms 61140 KB Output is correct
15 Correct 1905 ms 82556 KB Output is correct
16 Correct 1751 ms 75976 KB Output is correct
17 Correct 1876 ms 66896 KB Output is correct