Submission #726541

#	Time	Username	Problem	Language	Result	Execution time	Memory
726541		amunduzbaev	Prize (CEOI22_prize)	C++17	35 / 100	1955 ms	301736 KiB

Main

#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;
	for(int i=1;i<=k;i++){
		cout<<i<<" ";
		p.push_back(i);
	} 
	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];
	};
	
	if(q == k - 1){
		sort(p.begin(), p.end(), [&](int a, int b){
			return tin[0][a] < tin[0][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();
		
		for(int i=1;i<k;i++){
			int da, db; cin >> da >> db >> da >> db;
			int lca = Lca(0, p[i-1], p[i]);
			pos[lca].push_back(i - 1);
			ed.push_back({da, db});
		}
		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[0][a] > tin[0][b]) swap(a, b);
			int lca = Lca(0, 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]);
			cout<<res<<" "<<res<<endl;
		}
		cout.flush();
		
		return 0;
	}
	
	vector<ar<int, 2>> ed[2];
	vector<int> pref[2], pos[2][n + 1];
	vector<vector<int>> P(2, vector<int>(n + 1));
	vector<vector<int>> p_(2);
	
	for(int c=0;c<2;c++){
		sort(p.begin(), p.end(), [&](int a, int b){
			return tin[c][a] < tin[c][b];
		});
		p_[c] = p;
		for(int i=0;i<k;i++){
			P[c][p[i]] = i;
		}
		for(int i=1;i<k;i++){
			cout<<"? "<<p[i-1]<<" "<<p[i]<<endl;
		}
	}
	cout<<"! "<<endl;
	for(int c=0;c<2;c++){
		int TRASH = 0;
		for(int i=1;i<k;i++){
			int da, db; cin >> da >> db;
			if(!c){ cin >> TRASH >> TRASH; }
			else cin >> da >> db;
			int lca = Lca(c, p_[c][i-1], p_[c][i]);
			pos[c][lca].push_back(i-1);
			ed[c].push_back({da, db});
		}
		
		int sz = ed[c].size();
		pref[c].resize(sz);
		for(int i=0;i<sz;i++){
			//~ cout<<ed[c][i][0]<<" "<<ed[c][i][1]<<"\n";
			if(i){
				pref[c][i] = pref[c][i-1];
			}
			pref[c][i] += (ed[c][i][0] - ed[c][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){
		for(int c=0;c<2;c++){
			if(tin[c][a] > tin[c][b]) swap(a, b);
			int lca = Lca(c, a, b);
			int l = P[c][a], r = P[c][b];
			int j = *lower_bound(pos[c][lca].begin(), pos[c][lca].end(), l);
			int res = (j ? pref[c][j - 1] : 0) - (l ? pref[c][l - 1] : 0) + ed[c][j][0] + ed[c][j][1] - (pref[c][r - 1] - pref[c][j]);
			cout<<res<<" ";
		}
		cout<<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
0 3 13 5
3 1 5 10
1 0 7 10
0 3 13 5
1 2
2 3
1 3

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24