oj.uz

Submission #1046033

# Submission time Handle Problem Language Result Execution time Memory
1046033 2024-08-06T09:13:09 Z BuzzyBeez Regions (IOI09_regions) C++17
100 / 100
 1944 ms 82564 KB 
#pragma GCC optimize("O3,unroll-loops")
#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(2.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 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 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:34:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |  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 2 ms 11352 KB Output is correct
2 Correct 3 ms 11352 KB Output is correct
3 Correct 3 ms 11340 KB Output is correct
4 Correct 3 ms 11352 KB Output is correct
5 Correct 5 ms 11352 KB Output is correct
6 Correct 13 ms 11608 KB Output is correct
7 Correct 11 ms 11608 KB Output is correct
8 Correct 25 ms 11608 KB Output is correct
9 Correct 24 ms 12120 KB Output is correct
10 Correct 54 ms 12632 KB Output is correct
11 Correct 83 ms 12432 KB Output is correct
12 Correct 90 ms 13396 KB Output is correct
13 Correct 112 ms 12632 KB Output is correct
14 Correct 105 ms 12880 KB Output is correct
15 Correct 122 ms 14616 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 15332 KB Output is correct
2 Correct 591 ms 14160 KB Output is correct
3 Correct 862 ms 16508 KB Output is correct
4 Correct 153 ms 14412 KB Output is correct
5 Correct 283 ms 21704 KB Output is correct
6 Correct 383 ms 15448 KB Output is correct
7 Correct 550 ms 19788 KB Output is correct
8 Correct 776 ms 34024 KB Output is correct
9 Correct 1490 ms 54356 KB Output is correct
10 Correct 1587 ms 81460 KB Output is correct
11 Correct 1940 ms 77392 KB Output is correct
12 Correct 1303 ms 57936 KB Output is correct
13 Correct 1384 ms 57784 KB Output is correct
14 Correct 1641 ms 61132 KB Output is correct
15 Correct 1944 ms 82564 KB Output is correct
16 Correct 1832 ms 75856 KB Output is correct
17 Correct 1850 ms 66684 KB Output is correct