Submission #547749

#	Time	Username	Problem	Language	Result	Execution time	Memory
547749		NachoLibre	Regions (IOI09_regions)	C++17	100 / 100	4354 ms	86800 KiB

regions

#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 / 15
• Subtask 2: 85 / 85