oj.uz

Submission #547746

# Submission time Handle Problem Language Result Execution time Memory
547746 2022-04-11T15:01:26 Z NachoLibre Regions (IOI09_regions) C++17
55 / 100
 2709 ms 66616 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;
	}
}

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;
}

Compilation message

regions.cpp: In function 'int dfs(int, int)':
regions.cpp:24:1: warning: no return statement in function returning non-void [-Wreturn-type]
   24 | }
      | ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6096 KB Output is correct
2 Correct 4 ms 6096 KB Output is correct
3 Correct 6 ms 6096 KB Output is correct
4 Correct 8 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 25 ms 6224 KB Output is correct
8 Correct 31 ms 6352 KB Output is correct
9 Correct 25 ms 6736 KB Output is correct
10 Correct 61 ms 6900 KB Output is correct
11 Correct 72 ms 7376 KB Output is correct
12 Correct 84 ms 7936 KB Output is correct
13 Correct 152 ms 7916 KB Output is correct
14 Correct 177 ms 8656 KB Output is correct
15 Correct 250 ms 10584 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 24260 KB Execution killed with signal 11
2 Runtime error 46 ms 22876 KB Execution killed with signal 11
3 Runtime error 50 ms 27812 KB Execution killed with signal 11
4 Correct 164 ms 8516 KB Output is correct
5 Correct 337 ms 9680 KB Output is correct
6 Correct 851 ms 9944 KB Output is correct
7 Correct 1062 ms 11432 KB Output is correct
8 Correct 1012 ms 15432 KB Output is correct
9 Correct 1625 ms 18836 KB Output is correct
10 Correct 2457 ms 21536 KB Output is correct
11 Correct 2709 ms 19620 KB Output is correct
12 Runtime error 120 ms 41456 KB Execution killed with signal 11
13 Runtime error 107 ms 41052 KB Execution killed with signal 11
14 Runtime error 117 ms 41400 KB Execution killed with signal 11
15 Runtime error 133 ms 47544 KB Execution killed with signal 11
16 Runtime error 112 ms 66616 KB Execution killed with signal 11
17 Runtime error 102 ms 52088 KB Execution killed with signal 11