oj.uz

Submission #669094

# Submission time Handle Problem Language Result Execution time Memory
669094 2022-12-05T15:12:22 Z thiago_bastos Regions (IOI09_regions) C++17
100 / 100
 2174 ms 42524 KB 
#include "bits/stdc++.h"

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;

const int N = 2e5 + 10, K = 447, M = 25'010;

vector<int> adj[N];
vector<ii> Iregions[M];
int rPos[M], sub[N], myr[N], t, bigfrom[K][M], bigto[K][M];
int n, r, q;

void predfs(int u) {
	int in = t++;
	for(int v : adj[u]) predfs(v);
	Iregions[myr[u]].pb({in, -1});
	Iregions[myr[u]].pb({t - 1, 1});
}

void bigfromdfs(int big[], int cr, int n, int u) {
	big[myr[u]] += n;
	n += myr[u] == cr;
	for(int v : adj[u]) bigfromdfs(big, cr, n, v);
	n -= myr[u] == cr;
}

void bigtodfs(int big[], int cr, int u) {
	sub[u] = 0;
	for(int v : adj[u]) {
		bigtodfs(big, cr, v);
		sub[u] += sub[v];
	}
	big[myr[u]] += sub[u];
	sub[u] += myr[u] == cr;
}

void solve() {
	int bigCur = 0;

	cin >> n >> r >> q;

	cin >> myr[0];

	for(int i = 1; i < n; ++i) {
		int sup;
		cin >> sup >> myr[i];
		adj[sup - 1].pb(i); 
	}

	predfs(0);

	for(int i = 1; i <= r; ++i) {
		int m = Iregions[i].size() / 2;
		sort(all(Iregions[i]));
		if(1ll * m * m < n) continue;
		bigfromdfs(bigfrom[bigCur], i, 0, 0);
		bigtodfs(bigto[bigCur], i, 0);
		rPos[i] = bigCur++;
	}

	while(q--) {
		int r1, r2;

		cin >> r1 >> r2;

		int n_r1 = Iregions[r1].size() / 2;
		int n_r2 = Iregions[r2].size() / 2;

		if(1ll * n_r1 * n_r1 >= n) cout << bigfrom[rPos[r1]][r2] << endl;
		else if(1ll * n_r2 * n_r2 >= n) cout << bigto[rPos[r2]][r1] << endl;
		else {
			int i = 0, j = 0, opens = 0, pairs = 0;

			auto& I1 = Iregions[r1];
			auto& I2 = Iregions[r2];

			while(i < (int)I1.size() && j < (int)I2.size()) {
				if(I1[i] < I2[j]) opens -= I1[i++].sc;
				else pairs += I2[j++].sc == -1 ? opens : 0;
			}
			
			cout << pairs << endl;
		}
	}
}

int main() {
	ios_base :: sync_with_stdio(false);
	//cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5604 KB Output is correct
2 Correct 3 ms 5584 KB Output is correct
3 Correct 5 ms 5584 KB Output is correct
4 Correct 8 ms 5584 KB Output is correct
5 Correct 9 ms 5584 KB Output is correct
6 Correct 18 ms 5584 KB Output is correct
7 Correct 31 ms 5584 KB Output is correct
8 Correct 25 ms 5712 KB Output is correct
9 Correct 37 ms 6224 KB Output is correct
10 Correct 36 ms 6116 KB Output is correct
11 Correct 87 ms 6524 KB Output is correct
12 Correct 99 ms 6992 KB Output is correct
13 Correct 136 ms 6812 KB Output is correct
14 Correct 179 ms 7620 KB Output is correct
15 Correct 219 ms 11444 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 964 ms 11408 KB Output is correct
2 Correct 1022 ms 9884 KB Output is correct
3 Correct 1415 ms 13772 KB Output is correct
4 Correct 198 ms 7408 KB Output is correct
5 Correct 277 ms 9332 KB Output is correct
6 Correct 547 ms 12672 KB Output is correct
7 Correct 860 ms 14352 KB Output is correct
8 Correct 1004 ms 25584 KB Output is correct
9 Correct 1496 ms 15796 KB Output is correct
10 Correct 1837 ms 42524 KB Output is correct
11 Correct 2174 ms 15156 KB Output is correct
12 Correct 802 ms 17460 KB Output is correct
13 Correct 1092 ms 18096 KB Output is correct
14 Correct 1897 ms 20940 KB Output is correct
15 Correct 1748 ms 23484 KB Output is correct
16 Correct 1669 ms 32560 KB Output is correct
17 Correct 2147 ms 34588 KB Output is correct