oj.uz

Submission #726536

# Submission time Handle Problem Language Result Execution time Memory
726536 2023-04-19T03:59:04 Z amunduzbaev Prize (CEOI22_prize) C++17
10 / 100
 1154 ms 201604 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] = p;
		}
	}
	
	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];
			assert(!pos[lca].empty());
			//~ assert(pos[lca].back() <= l);
			int j = *lower_bound(pos[lca].begin(), pos[lca].end(), l);
			//~ assert(j < r);
			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();
	}
	
	//~ for(int c=0;c<1 + (q == 2 * k - 2);c++){
		//~ for(int i=1;i<k;i++){
			//~ cout<<"? "<<p[i-1]<<" "<<p[i]<<"\n";
		//~ }
	//~ }
}

/*

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 878 ms 198812 KB Output is correct
2 Correct 975 ms 201604 KB Output is correct
3 Correct 704 ms 147644 KB Output is correct
4 Correct 729 ms 146488 KB Output is correct
5 Correct 730 ms 148788 KB Output is correct
6 Correct 1099 ms 158492 KB Output is correct
7 Correct 1143 ms 158540 KB Output is correct
8 Correct 1154 ms 158188 KB Output is correct
9 Correct 815 ms 147572 KB Output is correct
10 Correct 839 ms 148412 KB Output is correct
11 Correct 707 ms 145968 KB Output is correct
12 Correct 728 ms 148408 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 722 ms 193476 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 688 ms 193348 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 271 ms 135256 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 277 ms 135332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -