oj.uz

Submission #727295

# Submission time Handle Problem Language Result Execution time Memory
727295 2023-04-20T11:38:04 Z amunduzbaev Prize (CEOI22_prize) C++17
81 / 100
 3073 ms 580572 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});
	}
	
	auto get = [&](int l, int r){
		if(l > r) return 0ll;
		return pref[r] - (l ? pref[l-1] : 0);
	};
	
	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 = get(l, j - 1) + ed[j][0] + ed[j][1] - get(j + 1, r - 1);
		//~ if(tin[1][a] > tin[1][b]) swap(a, b);
		//~ int lca = Lca(1, a, b);
		//~ int l = P[a], r = P[b], is = 0, res = 0;
		//~ for(int j=l;j<r;j++){
			//~ int tmp = Lca(1, p[j], p[j + 1]);
			//~ if(tmp == lca){
				//~ res += ed[j][0] + ed[j][1];
			//~ } else {
				//~ if(is) res += (ed[j][0] - ed[j][1]);
				//~ else res -= (ed[j][0] - ed[j][1]);
			//~ }
		//~ }
		lca = Lca(0, a, b);
		cout<<d[a] + d[b] - d[lca] * 2<<" "<<res<<endl;
	}
	cout.flush();
}

/*

4 4 3 2
-1 1 2 3
-1 1 2 2
0 14 0 3
0 9 0 3
0 6 3 4
1 3
4 3

7 6 5 5
-1 1 1 3 2 4 4
-1 1 2 3 1 5 3
1 5
4 5
2 5
5 7
4 7


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 1441 ms 327452 KB Output is correct
2 Correct 1472 ms 330112 KB Output is correct
3 Correct 1064 ms 276072 KB Output is correct
4 Correct 970 ms 274836 KB Output is correct
5 Correct 1082 ms 276920 KB Output is correct
6 Correct 1348 ms 287048 KB Output is correct
7 Correct 1394 ms 286792 KB Output is correct
8 Correct 1379 ms 286444 KB Output is correct
9 Correct 1006 ms 276068 KB Output is correct
10 Correct 1044 ms 276872 KB Output is correct
11 Correct 1037 ms 274336 KB Output is correct
12 Correct 1049 ms 276504 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1447 ms 329936 KB Output is correct
2 Correct 1411 ms 326576 KB Output is correct
3 Correct 1048 ms 276268 KB Output is correct
4 Correct 1089 ms 277312 KB Output is correct
5 Correct 1094 ms 276608 KB Output is correct
6 Correct 1520 ms 284948 KB Output is correct
7 Correct 1681 ms 287504 KB Output is correct
8 Correct 1604 ms 287540 KB Output is correct
9 Correct 1424 ms 286316 KB Output is correct
10 Correct 1392 ms 286780 KB Output is correct
11 Correct 1344 ms 284128 KB Output is correct
12 Correct 1323 ms 286660 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1226 ms 319340 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 2882 ms 569376 KB Output is correct
2 Correct 2929 ms 569376 KB Output is correct
3 Correct 1726 ms 465840 KB Output is correct
4 Correct 1742 ms 465936 KB Output is correct
5 Correct 1728 ms 465908 KB Output is correct
6 Correct 2389 ms 485664 KB Output is correct
7 Correct 2447 ms 485920 KB Output is correct
8 Correct 2466 ms 485740 KB Output is correct
9 Correct 2175 ms 482984 KB Output is correct
10 Correct 2149 ms 482932 KB Output is correct
11 Correct 2109 ms 482844 KB Output is correct
12 Correct 2147 ms 482832 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3073 ms 580572 KB Output is correct
2 Correct 3059 ms 580152 KB Output is correct
3 Correct 1938 ms 473840 KB Output is correct
4 Correct 2037 ms 476556 KB Output is correct
5 Correct 1926 ms 473460 KB Output is correct
6 Correct 2852 ms 496916 KB Output is correct
7 Correct 2796 ms 493932 KB Output is correct
8 Correct 2789 ms 495976 KB Output is correct
9 Correct 2430 ms 492892 KB Output is correct
10 Correct 2365 ms 492444 KB Output is correct
11 Correct 2423 ms 492468 KB Output is correct
12 Correct 2737 ms 493456 KB Output is correct