oj.uz

답안 #727294

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
727294 2023-04-20T11:33:47 Z amunduzbaev Prize (CEOI22_prize) C++17
19 / 100
 3500 ms 580648 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], 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.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3594 ms 327508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3548 ms 330000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1373 ms 319320 KB Output is correct
2 Correct 1415 ms 319228 KB Output is correct
3 Correct 1343 ms 267568 KB Output is correct
4 Correct 1287 ms 267524 KB Output is correct
5 Correct 1255 ms 267508 KB Output is correct
6 Correct 2001 ms 277564 KB Output is correct
7 Correct 2104 ms 277476 KB Output is correct
8 Correct 2167 ms 277632 KB Output is correct
9 Correct 2183 ms 276288 KB Output is correct
10 Correct 1955 ms 276020 KB Output is correct
11 Correct 1943 ms 276020 KB Output is correct
12 Correct 1921 ms 276024 KB Output is correct

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3272 ms 569380 KB Output is correct
2 Correct 3276 ms 569304 KB Output is correct
3 Execution timed out 3575 ms 466040 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3567 ms 580648 KB Time limit exceeded
2 Halted 0 ms 0 KB -