oj.uz

Submission #946305

# Submission time Handle Problem Language Result Execution time Memory
946305 2024-03-14T13:35:31 Z MinaRagy06 Prize (CEOI22_prize) C++17
100 / 100
 2473 ms 405192 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 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;
		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);
		return d[a] + d[b] - 2 * d[l];
	}
} t[2];
vector<array<int, 2>> toask;
vector<int> V;
void choose(vector<int> gud) {
	for (auto i : gud) {
		cout << i;
		if (i != gud.back()) cout << ' ';
	}
	cout << endl;
}
void ask(int a, int b) {
	toask.push_back({a, b});
}
vector<array<int, 6>> ret;
vector<array<int, 6>> get() {
	ret.clear();
	for (auto [a, b] : toask) {
		cout << "? " << a << ' ' << b << '\n';
	}
	cout << "!" << endl;
	for (auto [a, b] : toask) {
		int al1, bl1, al2, bl2;
		cin >> al1 >> bl1 >> al2 >> bl2;
		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);
			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();
	}
}
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;
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	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;	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 267144 KB Output is correct
2 Correct 1076 ms 271172 KB Output is correct
3 Correct 741 ms 239208 KB Output is correct
4 Correct 734 ms 238292 KB Output is correct
5 Correct 769 ms 242256 KB Output is correct
6 Correct 969 ms 247252 KB Output is correct
7 Correct 937 ms 248480 KB Output is correct
8 Correct 965 ms 246028 KB Output is correct
9 Correct 737 ms 240540 KB Output is correct
10 Correct 789 ms 242040 KB Output is correct
11 Correct 710 ms 237072 KB Output is correct
12 Correct 755 ms 241328 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1208 ms 271324 KB Output is correct
2 Correct 1101 ms 264788 KB Output is correct
3 Correct 791 ms 239912 KB Output is correct
4 Correct 838 ms 242812 KB Output is correct
5 Correct 838 ms 240532 KB Output is correct
6 Correct 1084 ms 243904 KB Output is correct
7 Correct 1248 ms 249552 KB Output is correct
8 Correct 1197 ms 249164 KB Output is correct
9 Correct 951 ms 247320 KB Output is correct
10 Correct 1077 ms 249420 KB Output is correct
11 Correct 930 ms 242616 KB Output is correct
12 Correct 985 ms 248392 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 799 ms 256496 KB Output is correct
2 Correct 780 ms 256568 KB Output is correct
3 Correct 571 ms 227468 KB Output is correct
4 Correct 549 ms 227472 KB Output is correct
5 Correct 552 ms 227640 KB Output is correct
6 Correct 722 ms 234192 KB Output is correct
7 Correct 700 ms 234236 KB Output is correct
8 Correct 689 ms 234468 KB Output is correct
9 Correct 642 ms 232336 KB Output is correct
10 Correct 648 ms 232400 KB Output is correct
11 Correct 664 ms 232128 KB Output is correct
12 Correct 633 ms 232116 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1936 ms 390108 KB Output is correct
2 Correct 1905 ms 390312 KB Output is correct
3 Correct 1220 ms 332292 KB Output is correct
4 Correct 1265 ms 332368 KB Output is correct
5 Correct 1250 ms 332416 KB Output is correct
6 Correct 1630 ms 346008 KB Output is correct
7 Correct 1591 ms 346052 KB Output is correct
8 Correct 1641 ms 346012 KB Output is correct
9 Correct 1422 ms 341760 KB Output is correct
10 Correct 1541 ms 341800 KB Output is correct
11 Correct 1585 ms 341688 KB Output is correct
12 Correct 1599 ms 341580 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2473 ms 405192 KB Output is correct
2 Correct 2394 ms 404472 KB Output is correct
3 Correct 1538 ms 343012 KB Output is correct
4 Correct 1563 ms 350252 KB Output is correct
5 Correct 1505 ms 342328 KB Output is correct
6 Correct 2258 ms 362368 KB Output is correct
7 Correct 2012 ms 356044 KB Output is correct
8 Correct 2082 ms 360516 KB Output is correct
9 Correct 1824 ms 354340 KB Output is correct
10 Correct 1773 ms 354352 KB Output is correct
11 Correct 1743 ms 353408 KB Output is correct
12 Correct 1853 ms 356412 KB Output is correct