oj.uz

Submission #867133

# Submission time Handle Problem Language Result Execution time Memory
867133 2023-10-27T17:53:30 Z Lalic Prize (CEOI22_prize) C++17
0 / 100
 641 ms 170272 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1e6+10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;

vector<vector<int>> adj;
vector<int> escolha;
int n, k, q, t;

int pai[22][MAXN], nvl[MAXN];

void build(int ver, int prev=0){
	nvl[ver]=nvl[prev]+1;

	for(auto u : adj[ver]){
		build(u, ver);
	}
}

void dfs(int ver){
	escolha.pb(ver);
	if((int)escolha.size()==k)
		return;

	for(auto u : adj[ver]){
		dfs(u);

		if((int)escolha.size()==k)
			return;
	}
}

int lca(int a, int b){
	if(nvl[a]>nvl[b])
		swap(a, b);

	int diff=nvl[b]-nvl[a];
	for(int i=0;i<=19;i++){
		if((diff&(1<<i))){
			b=pai[i][b];
		}
	}

	if(a==b)
		return a;

	for(int i=19;i>=0;i--){
		if(pai[i][a]!=pai[i][b]){
			a=pai[i][a];
			b=pai[i][b];
		}
	}

	return pai[0][a];
}

void solve(){
	cin >> n >> k >> q >> t;

	int root=-1;
	adj.resize(n+1);
	for(int i=1;i<=n;i++){
		int x; cin >> x;
		pai[0][i]=x;
		if(x==-1){
			pai[0][i]=i;
			root=i;
			continue;
		}
		adj[x].pb(i);
	}

	build(root);

	for(int i=1;i<=19;i++)
		for(int j=1;j<=n;j++)
			pai[i][j]=pai[i-1][pai[i-1][j]];

	for(int i=1;i<=n;i++){
		int x; cin >> x;
	}

	dfs(root);

	for(int i=0;i<k-1;i++)
		cout << escolha[i] << " ";
	cout << escolha[k-1] << endl;

	for(int i=1;i<k;i++)
		cout << "? " << escolha[0] << " " << escolha[i] << "\n";
	cout << "!" << endl;

	vector<int> dist(n+1);
	for(int i=1;i<k;i++){
		int baboseira[3];
		for(int j=0;j<3;j++)
			cin >> baboseira[j];
		cin >> dist[escolha[i]];
	}

	vector<pii> resp;
	for(int i=0;i<t;i++){
		int a, b; cin >> a >> b;
		int l=lca(a, b);

		cout << dist[a]+dist[b]-2*dist[l] << endl;
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int tt=1;
	// cin >> tt;
	while(tt--)
		solve();
}

/*
4 4 3 3
2 -1 2 1
2 -1 2 1

0 3 0 3
0 10 0 10
0 1 0 1
1 4
2 4
3 4
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 298 ms 126640 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 352 ms 126596 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 272 ms 126148 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 587 ms 169272 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 641 ms 170272 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -