oj.uz

Submission #838981

# Submission time Handle Problem Language Result Execution time Memory
838981 2023-08-28T12:14:53 Z sysia Prize (CEOI22_prize) C++17
10 / 100
 3087 ms 408200 KB 
//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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1775 ms 205508 KB Output is correct
2 Correct 1880 ms 205880 KB Output is correct
3 Correct 984 ms 179360 KB Output is correct
4 Correct 957 ms 179004 KB Output is correct
5 Correct 991 ms 180248 KB Output is correct
6 Correct 1475 ms 184064 KB Output is correct
7 Correct 1562 ms 184152 KB Output is correct
8 Correct 1479 ms 183920 KB Output is correct
9 Correct 980 ms 179096 KB Output is correct
10 Correct 980 ms 179912 KB Output is correct
11 Correct 969 ms 178512 KB Output is correct
12 Correct 999 ms 179812 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1146 ms 203724 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 2834 ms 407044 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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