Submission #677005

#	Time	Username	Problem	Language	Result	Execution time	Memory
677005		onjo0127	Prize (CEOI22_prize)	C++11	0 / 100	1532 ms	316632 KiB

Main

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

	for(int i=1; i<=T; i++) {
		int u, v; cin >> u >> v;
		cout << -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] << "\n";
	}
	cout.flush();
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24