oj.uz

Submission #727314

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

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 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;
		pos[Lca(1, p[i-1], p[i])].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});
	}
	
	auto get = [&](int l, int r){
		if(l > r) return 0ll;
		return pref[r] - (l ? pref[l-1] : 0);
	};
	
	for(int i=1;i<=n;i++){
		for(auto j : pos[i]){
			assert(Lca(1, p[j], p[j + 1]) == i);
		}
	}
	
	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];
		//~ assert(lower_bound(pos[lca].begin(), pos[lca].end(), l) != pos[lca].end());
		int pp = *lower_bound(pos[lca].begin(), pos[lca].end(), l);
		//~ assert(Lca(1, p[pp], p[pp + 1]) == lca);
		//~ int res = get(l, j - 1) + ed[j][0] + ed[j][1] - get(j + 1, r - 1);
		int is = 0, res = 0;
		for(int j=l;j<r;j++){
			int tmp = Lca(1, p[j], p[j + 1]);
			if(tmp == lca && !is){
				//~ assert(pp == j);
				res += ed[j][0] + ed[j][1];
				is = 1;
			} else {
				if(!is) res += (ed[j][0] - ed[j][1]);
				else res -= (ed[j][0] - ed[j][1]);
			}
		}
		lca = Lca(0, a, b);
		cout<<d[a] + d[b] - d[lca] * 2<<" "<<res<<endl;
	}
	cout.flush();
}

/*

4 4 3 2
-1 1 2 3
-1 1 2 2
0 14 0 3
0 9 0 3
0 6 3 4
1 3
4 3

7 6 5 5
-1 1 1 3 2 4 4
-1 1 2 3 1 5 3
1 5
4 5
2 5
5 7
4 7


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

*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:139:7: warning: unused variable 'pp' [-Wunused-variable]
  139 |   int pp = *lower_bound(pos[lca].begin(), pos[lca].end(), l);
      |       ^~
Main.cpp:123:7: warning: variable 'get' set but not used [-Wunused-but-set-variable]
  123 |  auto get = [&](int l, int r){
      |       ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3563 ms 327536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3606 ms 329844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1436 ms 319216 KB Output is correct
2 Correct 1519 ms 319232 KB Output is correct
3 Correct 1425 ms 267484 KB Output is correct
4 Correct 1352 ms 267660 KB Output is correct
5 Correct 1386 ms 267712 KB Output is correct
6 Correct 2399 ms 277428 KB Output is correct
7 Correct 2321 ms 277524 KB Output is correct
8 Correct 2245 ms 277488 KB Output is correct
9 Correct 2185 ms 276184 KB Output is correct
10 Correct 2322 ms 276052 KB Output is correct
11 Correct 2301 ms 276132 KB Output is correct
12 Correct 2120 ms 276008 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3174 ms 569288 KB Output is correct
2 Correct 3115 ms 569364 KB Output is correct
3 Execution timed out 3608 ms 465880 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3630 ms 580520 KB Time limit exceeded
2 Halted 0 ms 0 KB -