oj.uz

Submission #727296

# Submission time Handle Problem Language Result Execution time Memory
727296 2023-04-20T11:41:06 Z amunduzbaev Prize (CEOI22_prize) C++17
57 / 100
 3500 ms 580512 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];
		assert(lower_bound(pos[lca].begin(), pos[lca].end(), l) != pos[lca].end());
		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 1624 ms 327496 KB Output is correct
2 Correct 1514 ms 330080 KB Output is correct
3 Correct 1066 ms 276136 KB Output is correct
4 Correct 1059 ms 274980 KB Output is correct
5 Correct 1106 ms 277132 KB Output is correct
6 Correct 1533 ms 286824 KB Output is correct
7 Correct 1527 ms 286880 KB Output is correct
8 Correct 1436 ms 286544 KB Output is correct
9 Correct 1091 ms 276096 KB Output is correct
10 Correct 1127 ms 276732 KB Output is correct
11 Correct 1049 ms 274444 KB Output is correct
12 Correct 1230 ms 276604 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1688 ms 330008 KB Output is correct
2 Correct 1504 ms 326588 KB Output is correct
3 Correct 1118 ms 276180 KB Output is correct
4 Correct 1129 ms 277252 KB Output is correct
5 Correct 1176 ms 276484 KB Output is correct
6 Correct 1623 ms 284916 KB Output is correct
7 Correct 1687 ms 287404 KB Output is correct
8 Correct 1639 ms 287556 KB Output is correct
9 Correct 1389 ms 286264 KB Output is correct
10 Correct 1521 ms 286720 KB Output is correct
11 Correct 1520 ms 284008 KB Output is correct
12 Correct 1486 ms 286648 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1292 ms 319288 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 3098 ms 569232 KB Output is correct
2 Correct 3067 ms 569328 KB Output is correct
3 Correct 1819 ms 465916 KB Output is correct
4 Correct 1759 ms 465820 KB Output is correct
5 Correct 1761 ms 465856 KB Output is correct
6 Correct 2472 ms 485712 KB Output is correct
7 Correct 2489 ms 485736 KB Output is correct
8 Correct 2464 ms 485596 KB Output is correct
9 Correct 2201 ms 482936 KB Output is correct
10 Correct 2198 ms 482928 KB Output is correct
11 Correct 2152 ms 482684 KB Output is correct
12 Correct 2157 ms 482916 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3081 ms 580512 KB Output is correct
2 Execution timed out 3501 ms 580060 KB Time limit exceeded
3 Halted 0 ms 0 KB -