oj.uz

Submission #804347

# Submission time Handle Problem Language Result Execution time Memory
804347 2023-08-03T08:10:07 Z Arturgo Prize (CEOI22_prize) C++14
100 / 100
 3181 ms 554512 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1863 ms 279592 KB Output is correct
2 Correct 2029 ms 280040 KB Output is correct
3 Correct 1444 ms 251456 KB Output is correct
4 Correct 1433 ms 251252 KB Output is correct
5 Correct 1625 ms 251724 KB Output is correct
6 Correct 1871 ms 257176 KB Output is correct
7 Correct 1789 ms 257180 KB Output is correct
8 Correct 1743 ms 257120 KB Output is correct
9 Correct 1359 ms 251424 KB Output is correct
10 Correct 1432 ms 251596 KB Output is correct
11 Correct 1309 ms 251184 KB Output is correct
12 Correct 1423 ms 251480 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2135 ms 280016 KB Output is correct
2 Correct 1755 ms 279292 KB Output is correct
3 Correct 1436 ms 251496 KB Output is correct
4 Correct 1525 ms 251756 KB Output is correct
5 Correct 1435 ms 251436 KB Output is correct
6 Correct 1787 ms 256888 KB Output is correct
7 Correct 1920 ms 257204 KB Output is correct
8 Correct 1978 ms 257260 KB Output is correct
9 Correct 1890 ms 255916 KB Output is correct
10 Correct 2017 ms 256080 KB Output is correct
11 Correct 1705 ms 255616 KB Output is correct
12 Correct 1875 ms 256080 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 276456 KB Output is correct
2 Correct 641 ms 276464 KB Output is correct
3 Correct 455 ms 248280 KB Output is correct
4 Correct 460 ms 248276 KB Output is correct
5 Correct 488 ms 248232 KB Output is correct
6 Correct 598 ms 253888 KB Output is correct
7 Correct 547 ms 254080 KB Output is correct
8 Correct 576 ms 253912 KB Output is correct
9 Correct 621 ms 252600 KB Output is correct
10 Correct 513 ms 252488 KB Output is correct
11 Correct 570 ms 252576 KB Output is correct
12 Correct 530 ms 252604 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2009 ms 553060 KB Output is correct
2 Correct 1913 ms 553060 KB Output is correct
3 Correct 1210 ms 496704 KB Output is correct
4 Correct 1245 ms 496584 KB Output is correct
5 Correct 1168 ms 496512 KB Output is correct
6 Correct 1709 ms 507904 KB Output is correct
7 Correct 1701 ms 508040 KB Output is correct
8 Correct 1725 ms 507944 KB Output is correct
9 Correct 1758 ms 505108 KB Output is correct
10 Correct 1729 ms 505080 KB Output is correct
11 Correct 1617 ms 505204 KB Output is correct
12 Correct 1560 ms 505212 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3181 ms 554496 KB Output is correct
2 Correct 3068 ms 554512 KB Output is correct
3 Correct 2095 ms 497528 KB Output is correct
4 Correct 2277 ms 498108 KB Output is correct
5 Correct 2016 ms 497408 KB Output is correct
6 Correct 3065 ms 509512 KB Output is correct
7 Correct 2628 ms 508880 KB Output is correct
8 Correct 2884 ms 509228 KB Output is correct
9 Correct 2506 ms 506352 KB Output is correct
10 Correct 2578 ms 506084 KB Output is correct
11 Correct 2453 ms 506268 KB Output is correct
12 Correct 2655 ms 506404 KB Output is correct