oj.uz

Submission #727203

# Submission time Handle Problem Language Result Execution time Memory
727203 2023-04-20T08:05:40 Z amunduzbaev Prize (CEOI22_prize) C++17
35 / 100
 1588 ms 294784 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;
#define int ll

const int N = 5e5 + 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;
	cout.flush();
	vector<int> d(n + 1); 
	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;
	}
	
	int add = 0;
	for(auto x : p){
		if(x == R[0]){
			add = -d[x];
		}
	}
	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 1477 ms 292340 KB Output is correct
2 Correct 1451 ms 294784 KB Output is correct
3 Correct 973 ms 240716 KB Output is correct
4 Correct 988 ms 239712 KB Output is correct
5 Correct 1070 ms 241860 KB Output is correct
6 Correct 1401 ms 251668 KB Output is correct
7 Correct 1272 ms 251448 KB Output is correct
8 Correct 1540 ms 251336 KB Output is correct
9 Correct 1043 ms 240956 KB Output is correct
10 Correct 1040 ms 241372 KB Output is correct
11 Correct 1004 ms 239152 KB Output is correct
12 Correct 1062 ms 241272 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1479 ms 294756 KB Output is correct
2 Correct 1422 ms 291440 KB Output is correct
3 Correct 1057 ms 240880 KB Output is correct
4 Correct 1042 ms 241984 KB Output is correct
5 Correct 1074 ms 241340 KB Output is correct
6 Correct 1464 ms 249584 KB Output is correct
7 Correct 1539 ms 252140 KB Output is correct
8 Correct 1588 ms 252256 KB Output is correct
9 Correct 1348 ms 251168 KB Output is correct
10 Correct 1359 ms 251500 KB Output is correct
11 Correct 1292 ms 248776 KB Output is correct
12 Correct 1398 ms 251376 KB Output is correct

Subtask #3
0 / 19.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 338 ms 135284 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 316 ms 135360 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -