oj.uz

Submission #1043971

# Submission time Handle Problem Language Result Execution time Memory
1043971 2024-08-05T05:23:09 Z ㄴㄴ(#11063) Prize (CEOI22_prize) C++17
100 / 100
 1321 ms 322072 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MXN = 1000009;

int N, K, Q, T, l;
bool V[MXN];
vector<int> L;

struct Tree {
	vector<int> T[MXN];
	int rt, in[MXN], ou[MXN], ti = 0, P[22][MXN], D[MXN];
	void add(int p, int x) {
		P[0][x] = p;
		if(p == -1) rt = x, P[0][x] = x;
		else T[p].push_back(x);
	}
	void dfs(int x) {
		in[x] = ++ti;
		for(auto& it: T[x]) dfs(it);
		ou[x] = ti;
	}
	bool isup(int u, int v) {
		return in[u] <= in[v] && ou[u] >= ou[v];
	}
	int lca(int u, int v) {
		if(isup(u, v)) return u;
		if(isup(v, u)) return v;
		for(int i=l; i>=0; i--) if(!isup(P[i][u], v)) u = P[i][u];
		return P[0][u];
	}
	void inp() {
		for(int i=1; i<=N; i++) {
			int p; cin >> p;
			add(p, i);
		}
		dfs(rt);
		for(int i=1; (1<<i)<=N; i++) {
			for(int j=1; j<=N; j++) P[i][j] = P[i-1][P[i-1][j]];
			l = i;
		}
	}
} T1, T2;

int main() {
	cin >> N >> K >> Q >> T;
	T1.inp(); T2.inp();
	for(int i=1; i<=N; i++) if(T1.in[i] <= K) {
		cout << i << " ";
		L.push_back(i);
	}
	cout << "\n";
	cout.flush();

	assert((int)L.size() == K);
	sort(L.begin(), L.end(), [&](int p, int q) { return T2.in[p] < T2.in[q]; });
	for(int i=1; i<K; i++) cout << "? " << L[i-1] << " " << L[i] << "\n";
	cout << "!\n";
	cout.flush();
	
	for(int i=1; i<K; i++) {
		int u = L[i-1], v = L[i];
		int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;
		T1.D[v] = T1.D[u] - l1 + r1;

		int c2 = T2.lca(u, v);
		if(i == 1) {
			T2.D[c2] = 0;
			T2.D[u] = l2;
			T2.D[v] = r2;
		}
		else {
			T2.D[c2] = T2.D[u] - l2;
			T2.D[v] = T2.D[c2] + r2;
		}
	}

	vector<array<long long, 2>> ans;
	for(int i=1; i<=T; i++) {
		int u, v; cin >> u >> v;
		ans.push_back({-2LL * T1.D[T1.lca(u, v)] + T1.D[u] + T1.D[v], -2LL * T2.D[T2.lca(u, v)] + T2.D[u] + T2.D[v]});
	}
	for(auto [a, b]: ans) cout << a << " " << b << "\n";
	cout.flush();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 263156 KB Output is correct
2 Correct 539 ms 264416 KB Output is correct
3 Correct 493 ms 236248 KB Output is correct
4 Correct 515 ms 236088 KB Output is correct
5 Correct 530 ms 236128 KB Output is correct
6 Correct 583 ms 242728 KB Output is correct
7 Correct 646 ms 242676 KB Output is correct
8 Correct 596 ms 241692 KB Output is correct
9 Correct 491 ms 236016 KB Output is correct
10 Correct 647 ms 236108 KB Output is correct
11 Correct 497 ms 235052 KB Output is correct
12 Correct 592 ms 234980 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 264436 KB Output is correct
2 Correct 498 ms 264176 KB Output is correct
3 Correct 583 ms 235108 KB Output is correct
4 Correct 536 ms 236172 KB Output is correct
5 Correct 558 ms 236152 KB Output is correct
6 Correct 610 ms 242632 KB Output is correct
7 Correct 646 ms 242972 KB Output is correct
8 Correct 694 ms 242904 KB Output is correct
9 Correct 666 ms 240744 KB Output is correct
10 Correct 718 ms 240724 KB Output is correct
11 Correct 596 ms 240572 KB Output is correct
12 Correct 685 ms 240632 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 261936 KB Output is correct
2 Correct 426 ms 261648 KB Output is correct
3 Correct 318 ms 233776 KB Output is correct
4 Correct 363 ms 233904 KB Output is correct
5 Correct 359 ms 233336 KB Output is correct
6 Correct 402 ms 240452 KB Output is correct
7 Correct 373 ms 240336 KB Output is correct
8 Correct 510 ms 240408 KB Output is correct
9 Correct 367 ms 238276 KB Output is correct
10 Correct 374 ms 238276 KB Output is correct
11 Correct 421 ms 237996 KB Output is correct
12 Correct 394 ms 238232 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1199 ms 321572 KB Output is correct
2 Correct 1252 ms 320288 KB Output is correct
3 Correct 847 ms 264480 KB Output is correct
4 Correct 810 ms 264364 KB Output is correct
5 Correct 858 ms 264224 KB Output is correct
6 Correct 1139 ms 277176 KB Output is correct
7 Correct 1200 ms 277340 KB Output is correct
8 Correct 1094 ms 277480 KB Output is correct
9 Correct 1025 ms 273500 KB Output is correct
10 Correct 994 ms 273288 KB Output is correct
11 Correct 995 ms 273888 KB Output is correct
12 Correct 978 ms 273436 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1301 ms 321368 KB Output is correct
2 Correct 1243 ms 322072 KB Output is correct
3 Correct 970 ms 265604 KB Output is correct
4 Correct 1192 ms 265640 KB Output is correct
5 Correct 959 ms 265512 KB Output is correct
6 Correct 1298 ms 278388 KB Output is correct
7 Correct 1241 ms 278756 KB Output is correct
8 Correct 1283 ms 278328 KB Output is correct
9 Correct 1190 ms 273952 KB Output is correct
10 Correct 1263 ms 273884 KB Output is correct
11 Correct 1321 ms 274452 KB Output is correct
12 Correct 1256 ms 274564 KB Output is correct