oj.uz

Submission #838978

# Submission time Handle Problem Language Result Execution time Memory
838978 2023-08-28T12:10:15 Z sysia Prize (CEOI22_prize) C++17
10 / 100
 3500 ms 437884 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
 
void ckmin(int &a, int b) {a = min(a, b);}
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, deg, par, pre, post, dist;
	int n, root, tt = 0;
 
	void init(int _n){
		n = _n;
		g.resize(n+1);
		deg.resize(n+1);
		pre.resize(n+1);
		post.resize(n+1);
		par.assign(n+1, -1);
		dist.resize(n+1);
		depth.assign(n+1, 0);
		for (int i = 1; i<=n; i++){
			cin >> par[i];
			if (par[i] == -1) root = i;
			else g[par[i]].emplace_back(i, 0);
		}
		up.assign(n+1, vector<int>(K, root));
		for (int i = 1; i<=n; i++) deg[i] = (int)g[i].size();
		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);
		}
		post[v] = ++tt;
	}
 
	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 || ((int)g[i].size() && 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){
		debug(a, b, lca(a, 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);
	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 1706 ms 219744 KB Output is correct
2 Correct 1776 ms 220292 KB Output is correct
3 Correct 968 ms 190572 KB Output is correct
4 Correct 983 ms 190112 KB Output is correct
5 Correct 972 ms 191576 KB Output is correct
6 Correct 1417 ms 196088 KB Output is correct
7 Correct 1314 ms 196096 KB Output is correct
8 Correct 1399 ms 195916 KB Output is correct
9 Correct 984 ms 190448 KB Output is correct
10 Correct 975 ms 191408 KB Output is correct
11 Correct 952 ms 189512 KB Output is correct
12 Correct 985 ms 191136 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2020 ms 220272 KB Output is correct
2 Correct 1835 ms 219660 KB Output is correct
3 Runtime error 805 ms 191608 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1293 ms 218620 KB Output is correct
2 Correct 1403 ms 218616 KB Output is correct
3 Runtime error 632 ms 186072 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3253 ms 436756 KB Output is correct
2 Correct 3399 ms 436844 KB Output is correct
3 Runtime error 1462 ms 371828 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3565 ms 437884 KB Time limit exceeded
2 Halted 0 ms 0 KB -