Submission #946301

#	Time	Username	Problem	Language	Result	Execution time	Memory
946301		MinaRagy06	Prize (CEOI22_prize)	C++17	100 / 100	2361 ms	460344 KiB

Main

#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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24