oj.uz

Submission #727225

# Submission time Handle Problem Language Result Execution time Memory
727225 2023-04-20T08:53:19 Z amunduzbaev Prize (CEOI22_prize) C++17
81 / 100
 3289 ms 580496 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;
#define int ll

const int N = 1e6 + 5;
vector<int> G[2][N];
int tin[2][N], tout[2][N], par[2][N][20];
vector<int> pos[N];
int P[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k, q, T; cin >> n >> k >> q >> T;
	int R[2] {};
	for(int i=1;i<=n;i++){
		int p; cin >> p;
		if(~p){
			G[0][p].push_back(i);
		} else {
			R[0] = i;
		}
	}
	for(int i=1;i<=n;i++){
		int p; cin >> p;
		if(~p){
			G[1][p].push_back(i);
		} else {
			R[1] = i;
		}
	}
	
	for(int c=0;c<2;c++){
		int t = 0;
		tout[c][0] = N;
		function<void(int)> dfs = [&](int u){
			tin[c][u] = ++t;
			for(int j=1;j<20;j++){
				par[c][u][j] = par[c][par[c][u][j-1]][j-1];
			}
			for(auto x : G[c][u]){
				par[c][x][0] = u;
				dfs(x);
			}
			tout[c][u] = t;
		};
		dfs(R[c]);
	}
	
	vector<int> p;
	function<void(int)> dfs = [&](int u){
		if(tin[0][u] <= k){
			p.push_back(u);
		}
		for(auto x : G[0][u]){
			dfs(x);
		}
	};
	dfs(R[0]);
	for(auto x : p){
		cout<<x<<" ";
	} cout<<endl;
	
	auto is = [&](int t, int a, int b){
		return (tin[t][a] <= tin[t][b] && tin[t][b] <= tout[t][a]);
	};
	
	auto Lca = [&](int t, int a, int b){
		if(is(t, a, b)) return a;
		if(is(t, b, a)) return b;
		for(int j=19;~j;j--){
			if(!is(t, par[t][a][j], b)) a = par[t][a][j];
		}
		return par[t][a][0];
	};
	
	sort(p.begin(), p.end(), [&](int a, int b){
		return tin[1][a] < tin[1][b];
	});
	
	for(int i=0;i<k;i++){
		P[p[i]] = i;
	}
	for(int i=1;i<k;i++){
		cout<<"? "<<p[i-1]<<" "<<p[i]<<endl;
	}
	vector<ar<int, 2>> ed;
	cout<<"! "<<endl;
	
	vector<int> d(n + 1); 
	int add = 0;
	for(int i=1;i<k;i++){
		int dc, dd, da, db; cin >> dc >> dd >> da >> db;
		int lca = Lca(1, p[i-1], p[i]);
		pos[lca].push_back(i - 1);
		ed.push_back({da, db});
		
		d[p[i]] = d[p[i-1]] - dc + dd;
		if(p[i] == R[0]) add = -d[p[i]];
	}
	
	for(auto x : p){
		d[x] += add;
	}
	
	int sz = ed.size();
	vector<int> pref(sz);
	for(int i=0;i<sz;i++){
		if(i){
			pref[i] = pref[i-1];
		}
		pref[i] += (ed[i][0] - ed[i][1]);
	}
	
	vector<ar<int, 2>> Q;
	for(int i=0;i<T;i++){
		int a, b; cin >> a >> b;
		Q.push_back({a, b});
	}
	for(auto [a, b] : Q){
		if(tin[1][a] > tin[1][b]) swap(a, b);
		int lca = Lca(1, a, b);
		int l = P[a], r = P[b];
		int j = *lower_bound(pos[lca].begin(), pos[lca].end(), l);
		int res = (j ? pref[j - 1] : 0) - (l ? pref[l - 1] : 0) + ed[j][0] + ed[j][1] - (pref[r - 1] - pref[j]);
		lca = Lca(0, a, b);
		cout<<d[a] + d[b] - d[lca] * 2<<" "<<res<<endl;
	}
	cout.flush();
}

/*

9 3 4 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
10 0 0 1
0 3 13 5
1 2
2 4
1 4

9 3 2 3
2 -1 2 1 1 5 1 4 5
2 -1 2 1 1 5 1 4 5

3 0 3 0
3 1 3 1
1 2
2 3
1 3

*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1553 ms 327456 KB Output is correct
2 Correct 1635 ms 330144 KB Output is correct
3 Correct 1093 ms 276084 KB Output is correct
4 Correct 1062 ms 274928 KB Output is correct
5 Correct 1118 ms 277024 KB Output is correct
6 Correct 1481 ms 286776 KB Output is correct
7 Correct 1520 ms 286776 KB Output is correct
8 Correct 1544 ms 286340 KB Output is correct
9 Correct 1061 ms 275896 KB Output is correct
10 Correct 1154 ms 276796 KB Output is correct
11 Correct 1078 ms 274404 KB Output is correct
12 Correct 1162 ms 276496 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1743 ms 329840 KB Output is correct
2 Correct 1545 ms 326796 KB Output is correct
3 Correct 1299 ms 276104 KB Output is correct
4 Correct 1172 ms 277308 KB Output is correct
5 Correct 1134 ms 276548 KB Output is correct
6 Correct 1593 ms 284880 KB Output is correct
7 Correct 1587 ms 287516 KB Output is correct
8 Correct 1736 ms 287488 KB Output is correct
9 Correct 1434 ms 286336 KB Output is correct
10 Correct 1369 ms 286752 KB Output is correct
11 Correct 1332 ms 283960 KB Output is correct
12 Correct 1442 ms 286576 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1225 ms 319268 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3289 ms 569264 KB Output is correct
2 Correct 3029 ms 569272 KB Output is correct
3 Correct 1972 ms 465960 KB Output is correct
4 Correct 1839 ms 465860 KB Output is correct
5 Correct 1807 ms 465852 KB Output is correct
6 Correct 2591 ms 485728 KB Output is correct
7 Correct 2653 ms 485828 KB Output is correct
8 Correct 2750 ms 485576 KB Output is correct
9 Correct 2195 ms 482936 KB Output is correct
10 Correct 2350 ms 482964 KB Output is correct
11 Correct 2196 ms 482756 KB Output is correct
12 Correct 2209 ms 482980 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3053 ms 580496 KB Output is correct
2 Correct 3081 ms 580164 KB Output is correct
3 Correct 2013 ms 473896 KB Output is correct
4 Correct 2096 ms 476516 KB Output is correct
5 Correct 2058 ms 473332 KB Output is correct
6 Correct 3138 ms 496952 KB Output is correct
7 Correct 2797 ms 493904 KB Output is correct
8 Correct 2818 ms 495896 KB Output is correct
9 Correct 2421 ms 493004 KB Output is correct
10 Correct 2437 ms 492384 KB Output is correct
11 Correct 2558 ms 492260 KB Output is correct
12 Correct 2546 ms 493652 KB Output is correct