Submission #838981

#	Time	Username	Problem	Language	Result	Execution time	Memory
838981		sysia	Prize (CEOI22_prize)	C++17	10 / 100	3087 ms	408200 KiB

Main

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
typedef pair<int, int> T;
const int oo2 = 1e9+7;
const int K = 20;
 
struct graph{
	vector<vector<T>>g;
	vector<vector<int>>up;
	vector<int>depth, pre, dist;
	int n, root, tt = 0;
 
	void init(int _n){
		n = _n;
		g.resize(n+1);
		pre.resize(n+1);
		dist.resize(n+1);
		depth.assign(n+1, 0);
		for (int i = 1; i<=n; i++){
			int p; cin >> p;
			if (p == -1) root = i;
			else g[p].emplace_back(i, 0);
		}
		up.assign(n+1, vector<int>(K, root));
		dfs(root, root);
	}
 
	void dfs(int v, int pa){
		pre[v] = ++tt;
		up[v][0] = pa; //jump pointery sie liczy w kolejnosci preorder hshshs
		for (int i = 1; i<K; i++){
			up[v][i] = up[up[v][i-1]][i-1];
		}
		for (auto [x, __]: g[v]){
			if (x == pa) continue;
			depth[x] = depth[v]+1;
			dfs(x, v);
		}
	}
 
	int lca(int a, int b){
		if (depth[a] < depth[b]) swap(a, b);
		for (int i = K-1; i>=0; i--){
			if (depth[a] - (1<<i) >= depth[b]){
				a = up[a][i];
			}
		}
		if (a == b) return a;
		for (int i = K-1; i>=0; i--){
			if (up[a][i] != up[b][i]){
				a = up[a][i];
				b = up[b][i];
			}
		}
		return up[a][0];
	}

	void clear(){
		for (int i = 1; i<=n; i++) g[i].clear();
	}
 
	void bfs(){
		queue<int>q;
		int v = -1;
		for (int i = 1; i<=n; i++){
			if (v == -1 || depth[i] < depth[v]){
				v = i;
			}
		}
		debug(v);
		q.push(v);
		vector<bool>vis(n+1);
		vis[v] = 1;
		while ((int)q.size()){
			int u = q.front(); q.pop();
			for (auto [x, c]: g[u]){
				if (!vis[x]){
					dist[x] = dist[u]+c;
					vis[x] = 1;
					q.push(x);
				}
			}
		}
		debug(depth);
	}
 
	int get_dist(int a, int b){
		return dist[a] + dist[b] - 2 * dist[lca(a, b)];
	}
 
	void add(int a, int l, int c){
		if (c) {
			g[a].emplace_back(l, -c);
			g[l].emplace_back(a, c);
		}
	}
};
 
void solve(){
	int n, k, q, t; cin >> n >> k >> q >> t;
	array<graph, 2>g;
	g[0].init(n), g[1].init(n);
	vector<int>curr(n);
	iota(curr.begin(), curr.end(), 1);
	stable_sort(curr.begin(), curr.end(), [&](auto x, auto y){
		return g[0].pre[x] < g[0].pre[y];
	});
	while ((int)curr.size() > k) curr.pop_back();
	for (auto u: curr) cout << u << " ";
	cout << "\n"; cout.flush();	
	g[0].clear(); g[1].clear();
	vector<T>edges;
	for (int i = 1; i<(int)curr.size(); i++){
		cout << "? " << curr[i-1] << " " << curr[i] << "\n";
		edges.emplace_back(curr[i-1], curr[i]);
	}
	cout << "!\n"; cout.flush();
	for (auto [a, b]: edges){
		//b w poddrzewie a
		for (int rep = 0; rep < 2; rep++){
			int a1, b1; cin >> a1 >> b1;
			int lca = g[rep].lca(a, b);
			debug(a, b, lca, rep);
			g[rep].add(a, lca, a1);
			g[rep].add(b, lca, b1);
		}
	}
	g[0].bfs(); g[1].bfs();
	vector<T>que;
	while (t--){
		int a, b; cin >> a >> b;
		que.emplace_back(a, b);
	}
	for (auto [a, b]: que){
		cout << g[0].get_dist(a, b) << " " << g[1].get_dist(a, b) << "\n";
	}
	cout.flush();
}
 
int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	solve();
	
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24