oj.uz

Submission #677005

# Submission time Handle Problem Language Result Execution time Memory
677005 2023-01-02T03:28:37 Z onjo0127 Prize (CEOI22_prize) C++11
0 / 100
 1532 ms 316632 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;
		}
	}

	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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 721 ms 178452 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 769 ms 178584 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 644 ms 175516 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1482 ms 313192 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1532 ms 316632 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -