Submission #804347

#	Time	Username	Problem	Language	Result	Execution time	Memory
804347		Arturgo	Prize (CEOI22_prize)	C++14	100 / 100	3181 ms	554512 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
int N, K, Q, T;
 
struct Tree {
	vector<vector<int>> parents;
	vector<vector<int>> fils;
	vector<int> potentials;
	int root;
	
	vector<int> preorder;
	
	int cur;
	vector<int> debs, fins;
	
	void init_dfs(int u) {
		debs[u] = cur++;
		preorder.push_back(u);
		
		for(int v : fils[u]) {
			init_dfs(v);
		}
		
		fins[u] = cur++;
	}
	
	void init() {
		parents.resize(21);
		parents[0].resize(N);
		fils.resize(N);
		potentials = vector<int>(N, 0);
		debs.resize(N);
		fins.resize(N);
		
		for(int i = 0;i < N;i++) {
			cin >> parents[0][i];
			if(parents[0][i] != -1) {
				parents[0][i]--;
				fils[parents[0][i]].push_back(i);
			}
			else {
				root = i;
				parents[0][i] = i;
			}
		}
		
		for(int p = 1;p <= 20;p++) {
			parents[p].resize(N);
			for(int u = 0;u < N;u++) {
				parents[p][u] = parents[p - 1][parents[p - 1][u]];
			}
		}
		
		cur = 0;
		init_dfs(root);
	}
	
	bool estParent(int a, int b) {
		return debs[a] <= debs[b] && fins[b] <= fins[a];
	}
	
	int lca(int a, int b) {
		int p = 20;
		
		while(p != -1) {
			if(!estParent(parents[p][a], b)) 
				a = parents[p][a];
			p--;
		}
		
		if(!estParent(a, b)) a = parents[0][a];
		return a;
	}
};
 
Tree t1, t2;
 
bool is_selected[1000 * 1000];
 
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> N >> K >> Q >> T;
	
	t1.init();
	t2.init();
	
	vector<int> preorder = t1.preorder;
	preorder.resize(K);
	
	// We give the K vertices we want
	for(int val : preorder) {
		cout << 1 + val << " ";
		is_selected[val] = true;
	}
	cout << "\n";
	cout << flush;
	
	vector<int> preorder_t2 = t2.preorder;
	
	vector<pair<int, int>> queries;
	
	int last = -1;
	for(int v : preorder_t2) {
		if(is_selected[v]) {
			if(last != -1) {
				queries.push_back({last, v});
			}
			last = v;
		}
	}
	
	for(pair<int, int> query : queries) {
		cout << "? " << query.first + 1 << " "<< query.second + 1 << "\n";
	}
	
	cout << "!\n";
	cout << flush;
	
	for(pair<int, int> query : queries) {
		int d1a, d1b, d2a, d2b;
		cin >> d1a >> d1b >> d2a >> d2b;
		
		int p1 = t1.lca(query.first, query.second);
		int p2 = t2.lca(query.first, query.second);
		
		t1.potentials[p1] = t1.potentials[query.first] - d1a;
		t1.potentials[query.second] = t1.potentials[p1] + d1b;
		t2.potentials[p2] = t2.potentials[query.first] - d2a;
		t2.potentials[query.second] = t2.potentials[p2] + d2b;	
	}
	
	vector<pair<int, int>> reqs;
	
	for(int i = 0;i < T;i++) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		reqs.push_back({x, y});
	}
		
	for(pair<int, int> req : reqs) {
		int x = req.first;
		int y = req.second;
		
		int d1 = t1.potentials[x] + t1.potentials[y]
		- 2 * t1.potentials[t1.lca(x, y)];
		int d2 = t2.potentials[x] + t2.potentials[y]
		- 2 * t2.potentials[t2.lca(x, y)];
		
		cout << d1 << " " << d2 << "\n";
	}
	cout << flush;
	return 0;
}

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