oj.uz

Submission #727253

# Submission time Handle Problem Language Result Execution time Memory
727253 2023-04-20T10:20:48 Z amunduzbaev Prize (CEOI22_prize) C++17
57 / 100
 3500 ms 580684 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;
#define int ll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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 i=1;i<=n;i++){
		shuffle(G[0][i].begin(), G[0][i].end(), rng);
		shuffle(G[1][i].begin(), G[1][i].end(), rng);
	}
	
	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 1475 ms 327488 KB Output is correct
2 Correct 1637 ms 330032 KB Output is correct
3 Correct 1145 ms 276028 KB Output is correct
4 Correct 1137 ms 274932 KB Output is correct
5 Correct 1212 ms 276952 KB Output is correct
6 Correct 1598 ms 286788 KB Output is correct
7 Correct 1557 ms 286892 KB Output is correct
8 Correct 1517 ms 286492 KB Output is correct
9 Correct 1116 ms 276000 KB Output is correct
10 Correct 1105 ms 276732 KB Output is correct
11 Correct 1119 ms 274424 KB Output is correct
12 Correct 1132 ms 276496 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1559 ms 329988 KB Output is correct
2 Correct 1504 ms 326660 KB Output is correct
3 Correct 1189 ms 276328 KB Output is correct
4 Correct 1172 ms 277372 KB Output is correct
5 Correct 1151 ms 276668 KB Output is correct
6 Correct 1646 ms 285064 KB Output is correct
7 Correct 1626 ms 287272 KB Output is correct
8 Correct 1900 ms 287496 KB Output is correct
9 Correct 1471 ms 286500 KB Output is correct
10 Correct 1515 ms 286724 KB Output is correct
11 Correct 1365 ms 284008 KB Output is correct
12 Correct 1501 ms 286736 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1297 ms 319224 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 3198 ms 569240 KB Output is correct
2 Correct 2966 ms 569340 KB Output is correct
3 Correct 1941 ms 465968 KB Output is correct
4 Correct 1970 ms 465864 KB Output is correct
5 Correct 1903 ms 465732 KB Output is correct
6 Correct 2734 ms 485776 KB Output is correct
7 Correct 2937 ms 485984 KB Output is correct
8 Correct 2731 ms 485772 KB Output is correct
9 Correct 2372 ms 482788 KB Output is correct
10 Correct 2429 ms 482908 KB Output is correct
11 Correct 2261 ms 482944 KB Output is correct
12 Correct 2408 ms 482872 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3118 ms 580684 KB Output is correct
2 Execution timed out 3523 ms 580384 KB Time limit exceeded
3 Halted 0 ms 0 KB -