oj.uz

Submission #547749

# Submission time Handle Problem Language Result Execution time Memory
547749 2022-04-11T15:04:16 Z NachoLibre Regions (IOI09_regions) C++17
100 / 100
 4354 ms 86800 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;

const int N = 200005, C = 500, R = 25004, Q = N;
int n, r, q, h[N], s[N], c[R], r1, r2, gd, e[N], o[N];
vector<int> v[N], ve[R];
vector<array<int, 2> > veo[R];
map<array<int, 2>, int> zd, qd;

int dfs(int x = 1, int zdc = 0) {
	if(h[x] == gd) zdc += 1;
	int qdc = (h[x] == gd);
	for(int y : v[x]) {
		qdc += dfs(y, zdc);
	}
	if(h[x] != gd) {
		zd[{gd, h[x]}] += zdc;
		qd[{h[x], gd}] += qdc;
	}
	return qdc;
}

int dfsi(int x = 1) {
	int z = e[x] + 1;
	for(int y : v[x]) {
		e[y] = z;
		z = dfsi(y);
	}
	o[x] = z - 1;
	return z;
}

bool sbl(int &a, array<int, 2> &b) {
	int y = (b[1] ? o[b[0]] : e[b[0]]);
	if(e[a] < y) return 1;
	if(e[a] > y) return 0;
	return b[1];
}

int mergeboom(vector<array<int, 2> > &a, vector<int> &b) {
	int i1 = 0, i2 = 0, c = 0, x = 0;
	while(i1 < sz(a) || i2 < sz(b)) {
		if(i1 == sz(a) || (i2 != sz(b) && sbl(b[i2], a[i1]))) {
			// cout << "b ";
			x += c;
			i2 += 1;
		} else {
			// cout << "a ";
			c += (a[i1][1] ? -1 : 1);
			i1 += 1;
		}
	}
	return x;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	#ifdef x
	freopen("x.txt", "r", stdin);
	#endif
	cin >> n >> r >> q >> h[1];
	c[h[1]] += 1;
	for(int i = 2; i <= n; ++i) {
		cin >> s[i] >> h[i];
		c[h[i]] += 1;
		v[s[i]].push_back(i);
	}
	dfsi();
	for(int i = 1; i <= n; ++i) {
		ve[h[i]].push_back(i);
		veo[h[i]].push_back({i, 0});
		veo[h[i]].push_back({i, 1});
	}
	for(int i = 1; i <= r; ++i) {
		if(c[i] <= C) {
			sort(all(ve[i]), [&](auto a, auto b) {
				return e[a] < e[b];
			});
			sort(all(veo[i]), [&](auto a, auto b) {
				int x = (a[1] ? o[a[0]] : e[a[0]]);
				int y = (b[1] ? o[b[0]] : e[b[0]]);
				return x < y;
			});
		}
	}
	// for(int i = 1; i <= r; ++i) {
	// 	cout << i << " - ";
	// 	for(int x : ve[i]) {
	// 		cout << x << " ";
	// 	} cout << "\n";
	// 	cout << "    ";
	// 	for(array<int, 2> x : veo[i]) {
	// 		cout << x[0] << " ";
	// 	} cout << "\n";
	// }
	for(gd = 1; gd <= r; ++gd) {
		if(c[gd] > C) {
			dfs();
		}
	}
	for(int i = 1; i <= q; ++i) {
		cin >> r1 >> r2;
		if(c[r1] > C) {
			cout << zd[{r1, r2}];
		} else if(c[r2] > C) {
			cout << qd[{r1, r2}];
		} else {
			cout << mergeboom(veo[r1], ve[r2]);
		}
		cout << "\n" << flush;
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6096 KB Output is correct
2 Correct 4 ms 6096 KB Output is correct
3 Correct 5 ms 6096 KB Output is correct
4 Correct 9 ms 6096 KB Output is correct
5 Correct 14 ms 6224 KB Output is correct
6 Correct 21 ms 6224 KB Output is correct
7 Correct 29 ms 6224 KB Output is correct
8 Correct 34 ms 6384 KB Output is correct
9 Correct 51 ms 6736 KB Output is correct
10 Correct 80 ms 6924 KB Output is correct
11 Correct 131 ms 7376 KB Output is correct
12 Correct 130 ms 7936 KB Output is correct
13 Correct 169 ms 7904 KB Output is correct
14 Correct 197 ms 8660 KB Output is correct
15 Correct 244 ms 10576 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1006 ms 13116 KB Output is correct
2 Correct 1006 ms 11588 KB Output is correct
3 Correct 1518 ms 16172 KB Output is correct
4 Correct 227 ms 8528 KB Output is correct
5 Correct 303 ms 9680 KB Output is correct
6 Correct 774 ms 9940 KB Output is correct
7 Correct 978 ms 11468 KB Output is correct
8 Correct 911 ms 15432 KB Output is correct
9 Correct 1568 ms 18844 KB Output is correct
10 Correct 2087 ms 21548 KB Output is correct
11 Correct 2382 ms 19612 KB Output is correct
12 Correct 1024 ms 24124 KB Output is correct
13 Correct 1574 ms 24932 KB Output is correct
14 Correct 4335 ms 67812 KB Output is correct
15 Correct 2262 ms 34252 KB Output is correct
16 Correct 2301 ms 45024 KB Output is correct
17 Correct 4354 ms 86800 KB Output is correct