oj.uz

Submission #946301

# Submission time Handle Problem Language Result Execution time Memory
946301 2024-03-14T13:32:39 Z MinaRagy06 Prize (CEOI22_prize) C++17
100 / 100
 2361 ms 460344 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()

const int N = 1'000'005;
struct gradingtree {
	int n, k, root;
	vector<int> P, W;
	int t;
	int st[N], en[N], anc[N][20];
	vector<array<int, 2>> adj[N];
	int d[N];
	void dfs(int i, int p, int dep) {
		anc[i][0] = p;
		d[i] = dep;
		for (int j = 1; j < 20; j++) {
			anc[i][j] = anc[anc[i][j - 1]][j - 1];
		}
		st[i] = t++;
		for (auto [nxt, w] : adj[i]) {
			dfs(nxt, i, dep + w);
		}
		en[i] = t - 1;
	}
	void init(int _n, int _k, vector<int> &_p, vector<int> &_w) {
		n = _n, k = _k, P = _p, W = _w;
		for (int i = 1; i <= n; i++) {
			if (P[i] == -1) {
				root = i;
			} else {
				adj[P[i]].push_back({i, W[i]});
			}
		}
		dfs(root, root, 0);
	}
	int lca(int a, int b) {
		if (st[a] <= st[b] && en[b] <= en[a]) {
			return a;
		}
		for (int j = 19; j >= 0; j--) {
			int c = anc[a][j];
			if (!(st[c] <= st[b] && en[b] <= en[c])) {
				a = c;
			}
		}
		return anc[a][0];
	}
	int dist(int a, int b) {
		int l = lca(a, b);
		// 		cout << "> " << a << ' ' << b << ": " << d[a] + d[b] - 2 * d[l] << '\n';
		return d[a] + d[b] - 2 * d[l];
	}
} gt[2];

struct tree {
	int n, k, root;
	vector<int> P, adj[N], gud;
	bool vis[N];
	int t;
	int st[N], en[N], anc[N][20];
	void dfs(int i, int p) {
		if (SZ(gud) < k) gud.push_back(i);
		anc[i][0] = p;
		for (int j = 1; j < 20; j++) {
			anc[i][j] = anc[anc[i][j - 1]][j - 1];
		}
		st[i] = t++;
		for (auto nxt : adj[i]) {
			dfs(nxt, i);
		}
		en[i] = t - 1;
	}
	void init(int _n, int _k, vector<int> &_p) {
		n = _n, k = _k, P = _p;
		for (int i = 1; i <= n; i++) {
			vis[i] = 0;
			if (P[i] == -1) {
				root = i;
			} else {
				adj[P[i]].push_back(i);
			}
		}
		dfs(root, root);
	}
	int lca(int a, int b) {
		if (st[a] <= st[b] && en[b] <= en[a]) {
			return a;
		}
		for (int j = 19; j >= 0; j--) {
			int c = anc[a][j];
			if (!(st[c] <= st[b] && en[b] <= en[c])) {
				a = c;
			}
		}
		return anc[a][0];
	}
	vector<array<int, 2>> adj2[N];
	int d[N];
	void dfs2(int i, int c) {
		d[i] = c;
		vis[i] = 1;
// 		cout << i << ' ' << d[i] << '\n';
		for (auto [nxt, w] : adj2[i]) {
			if (vis[nxt]) continue;
			dfs2(nxt, c + w);
		}
	}
	void process2() {
		int mn = 1e9, node = -1;
		for (auto i : gud) {
			if (st[i] < mn) {
				mn = st[i];
				node = i;
			}
		}
		for (int i = 1; i < SZ(gud); i++) {
			int x = lca(gud[i - 1], gud[i]);
			if (st[x] < mn) {
				mn = st[x];
				node = x;
			}
		}
		dfs2(node, 0);
	}
	int dist(int a, int b) {
		int l = lca(a, b);
// 		cout << a << ' ' << b << ' ' << l << '\n';
		return d[a] + d[b] - 2 * d[l];
	}
} t[2];
vector<array<int, 2>> toask;
vector<int> V;
void choose(vector<int> gud) {
#ifndef MINA
	for (auto i : gud) {
		cout << i;
		if (i != gud.back()) cout << ' ';
	}
	cout << endl;
#else
	V = gud;
#endif
}
void ask(int a, int b) {
	toask.push_back({a, b});
}
vector<array<int, 6>> ret;
vector<array<int, 6>> get() {
	ret.clear();
#ifndef MINA
	for (auto [a, b] : toask) {
		cout << "? " << a << ' ' << b << '\n';
	}
	cout << "!" << endl;
#endif
	for (auto [a, b] : toask) {
		int al1, bl1, al2, bl2;
#ifndef MINA
		cin >> al1 >> bl1 >> al2 >> bl2;
#else
		int l1 = gt[0].lca(a, b), l2 = gt[1].lca(a, b);
		al1 = gt[0].dist(a, l1);
		bl1 = gt[0].dist(b, l1);
		al2 = gt[1].dist(a, l2);
		bl2 = gt[1].dist(b, l2);
		// 		cout << "? " << a << ' ' << b << "(" << l1 << ", " << l2 << "): " << al1 << ' ' << bl1 << ' ' << al2 << ' ' << bl2 << '\n';
#endif
		ret.push_back({a, b, al1, bl1, al2, bl2});
	}
	return ret;
}
int n, m;
vector<array<int, 6>> v;
void init(int _n, int _m, vector<int> p1, vector<int> p2) {
	n = _n, m = _m;
	t[0].init(n, m, p1);
	t[1].init(n, m, p2);
	sort(t[0].gud.begin(), t[0].gud.end(), [&] (int x, int y) {return t[1].st[x] < t[1].st[y];});
	vector<int> gud;
	gud = t[1].gud = t[0].gud;
	choose(gud);
	for (int i = 1; i < SZ(gud); i++) {
		ask(gud[i - 1], gud[i]);
	}
	v = get();
	for (auto [a, b, al1, bl1, al2, bl2] : v) {
		int al[2] = {al1, al2};
		int bl[2] = {bl1, bl2};
		for (int k = 0; k < 2; k++) {
			int l = t[k].lca(a, b);
// 			cout << l << " -> " << a << ": " << al[k] << '\n';
// 			cout << a << " -> " << l << ": " << -al[k] << '\n';
// 			cout << l << " -> " << b << ": " << bl[k] << '\n';
// 			cout << b << " -> " << l << ": " << -bl[k] << '\n';
			t[k].adj2[l].push_back({a, al[k]});
			t[k].adj2[a].push_back({l, -al[k]});

			t[k].adj2[l].push_back({b, bl[k]});
			t[k].adj2[b].push_back({l, -bl[k]});
		}
	}
	for (int k = 0; k < 2; k++) {
		t[k].process2();
		// 		cout << "=========\n";
	}
}
array<int, 2> query(int x, int y) {
	return {t[0].dist(x, y), t[1].dist(x, y)};
}
vector<int> p1, p2, w1, w2;
vector<array<int, 2>> ans;
void solve() {
	int _n, _k, _q, _t;
	cin >> _n >> _k >> _q >> _t;
	p1.resize(_n + 1);
	p2.resize(_n + 1);
	for (int i = 1; i <= _n; i++) {
		cin >> p1[i];
	}
	for (int i = 1; i <= _n; i++) {
		cin >> p2[i];
	}
	init(_n, _k, p1, p2);
	while (_t--) {
		int a, b;
		cin >> a >> b;
		ans.push_back(query(a, b));
	}
	for (auto [d1, d2] : ans) {
		cout << d1 << ' ' << d2 << '\n';
	}
	cout << endl;	
}
mt19937 rnd(2006);
int rng(int l, int r) {
	return rnd() % (r - l + 1) + l;
}
void grader() {
	int _n, _k, _q, _t;
	cin >> _n >> _k >> _q >> _t;
	p1.resize(_n + 1);
	p2.resize(_n + 1);
	w1.resize(_n + 1);
	w2.resize(_n + 1);
	for (int i = 1; i <= _n; i++) {
		cin >> p1[i];
	}
	for (int i = 1; i <= _n; i++) {
		cin >> p2[i];
	}
	for (int i = 1; i <= _n; i++) {
		cin >> w1[i];
	}
	for (int i = 1; i <= _n; i++) {
		cin >> w2[i];
	}
	gt[0].init(_n, _k, p1, w1);
	gt[1].init(_n, _k, p2, w2);
	init(_n, _k, p1, p2);
	while (_t--) {
		int a = rng(0, V.size() - 1), b = rng(0, V.size() - 1);
		a = V[a], b = V[b];
		array<int, 2> val = query(a, b);
		array<int, 2> cval = {gt[0].dist(a, b), gt[1].dist(a, b)};
		if (val != cval) {
			cout << a << ' ' << b << ": " << val[0] << ' ' << cval[1] << '\n';
			cout << "WA\n";
			exit(0);
		}
	}
	cout << "OK\n";
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
#ifdef MINA
	grader();
#else
	solve();
#endif
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1123 ms 322912 KB Output is correct
2 Correct 1042 ms 327264 KB Output is correct
3 Correct 750 ms 294340 KB Output is correct
4 Correct 738 ms 293712 KB Output is correct
5 Correct 777 ms 298140 KB Output is correct
6 Correct 1075 ms 302412 KB Output is correct
7 Correct 994 ms 303520 KB Output is correct
8 Correct 954 ms 301996 KB Output is correct
9 Correct 789 ms 295156 KB Output is correct
10 Correct 774 ms 297384 KB Output is correct
11 Correct 731 ms 292380 KB Output is correct
12 Correct 814 ms 296796 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1330 ms 326492 KB Output is correct
2 Correct 1188 ms 320192 KB Output is correct
3 Correct 910 ms 294428 KB Output is correct
4 Correct 900 ms 298196 KB Output is correct
5 Correct 845 ms 296276 KB Output is correct
6 Correct 1318 ms 299004 KB Output is correct
7 Correct 1286 ms 303808 KB Output is correct
8 Correct 1227 ms 304460 KB Output is correct
9 Correct 1067 ms 302856 KB Output is correct
10 Correct 1081 ms 304176 KB Output is correct
11 Correct 988 ms 298948 KB Output is correct
12 Correct 1058 ms 303696 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 822 ms 311876 KB Output is correct
2 Correct 831 ms 312192 KB Output is correct
3 Correct 558 ms 282860 KB Output is correct
4 Correct 591 ms 282864 KB Output is correct
5 Correct 528 ms 282872 KB Output is correct
6 Correct 762 ms 289596 KB Output is correct
7 Correct 716 ms 289628 KB Output is correct
8 Correct 735 ms 289848 KB Output is correct
9 Correct 650 ms 287500 KB Output is correct
10 Correct 669 ms 287484 KB Output is correct
11 Correct 633 ms 287516 KB Output is correct
12 Correct 678 ms 287504 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1969 ms 445188 KB Output is correct
2 Correct 2017 ms 445208 KB Output is correct
3 Correct 1261 ms 387140 KB Output is correct
4 Correct 1260 ms 386876 KB Output is correct
5 Correct 1228 ms 387164 KB Output is correct
6 Correct 1762 ms 400428 KB Output is correct
7 Correct 1761 ms 400704 KB Output is correct
8 Correct 1719 ms 400388 KB Output is correct
9 Correct 1448 ms 396412 KB Output is correct
10 Correct 1522 ms 396364 KB Output is correct
11 Correct 1451 ms 396408 KB Output is correct
12 Correct 1567 ms 396456 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2361 ms 460344 KB Output is correct
2 Correct 2342 ms 460108 KB Output is correct
3 Correct 1461 ms 397904 KB Output is correct
4 Correct 1624 ms 403884 KB Output is correct
5 Correct 1522 ms 396584 KB Output is correct
6 Correct 2169 ms 416808 KB Output is correct
7 Correct 2047 ms 410516 KB Output is correct
8 Correct 2140 ms 414028 KB Output is correct
9 Correct 1806 ms 408956 KB Output is correct
10 Correct 1819 ms 408624 KB Output is correct
11 Correct 1811 ms 408548 KB Output is correct
12 Correct 1773 ms 411352 KB Output is correct