oj.uz

Submission #726541

# Submission time Handle Problem Language Result Execution time Memory
726541 2023-04-19T04:27:31 Z amunduzbaev Prize (CEOI22_prize) C++17
35 / 100
 1955 ms 301736 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1425 ms 284964 KB Output is correct
2 Correct 1370 ms 287724 KB Output is correct
3 Correct 991 ms 233696 KB Output is correct
4 Correct 967 ms 232528 KB Output is correct
5 Correct 1028 ms 234828 KB Output is correct
6 Correct 1410 ms 244864 KB Output is correct
7 Correct 1391 ms 244656 KB Output is correct
8 Correct 1357 ms 244224 KB Output is correct
9 Correct 972 ms 233576 KB Output is correct
10 Correct 1002 ms 234456 KB Output is correct
11 Correct 931 ms 231840 KB Output is correct
12 Correct 989 ms 234164 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1554 ms 301736 KB Output is correct
2 Correct 1583 ms 296424 KB Output is correct
3 Correct 1212 ms 269372 KB Output is correct
4 Correct 1263 ms 271604 KB Output is correct
5 Correct 1201 ms 269832 KB Output is correct
6 Correct 1728 ms 271156 KB Output is correct
7 Correct 1955 ms 274528 KB Output is correct
8 Correct 1897 ms 274788 KB Output is correct
9 Correct 1600 ms 273564 KB Output is correct
10 Correct 1596 ms 274424 KB Output is correct
11 Correct 1428 ms 270460 KB Output is correct
12 Correct 1513 ms 274176 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1123 ms 279424 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 285 ms 135308 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 313 ms 135364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -