Submission #727294

#	Time	Username	Problem	Language	Result	Execution time	Memory
727294		amunduzbaev	Prize (CEOI22_prize)	C++17	19 / 100	3594 ms	580648 KiB

Main

    #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], is = 0, res = 0;
    		for(int j=l;j<r;j++){
    			int tmp = Lca(1, p[j], p[j + 1]);
    			if(tmp == lca && !is){
                  	is = 1;
    				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]);
    			}
    		}
    		//~ 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: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 19 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24