Submission #1186816

#TimeUsernameProblemLanguageResultExecution timeMemory
1186816user192837Prize (CEOI22_prize)C++17
0 / 100
2701 ms397528 KiB
#include <bits/stdc++.h> #define ar array using namespace std; vector <vector <vector <int>>> g, st; vector <vector <int>> d, checkpoint; vector <int> taken; int root[2], qd; void dfs1(int x, int par) { d[qd][x] = d[qd][par] + 1, st[qd][0][x] = par; for (int i = 1; i < 20; i++) st[qd][i][x] = st[qd][i - 1][st[qd][i - 1][x]]; for (int y : g[qd][x]) if (y != par) dfs1(y, x); } int jump(int x, int k) { int i = 0; while (k) { if (k & 1) x = st[qd][i][x]; k >>= 1; i++; } return x; } int lca(int a, int b) { if (d[qd][a] > d[qd][b]) swap(a, b); b = jump(b, d[qd][b] - d[qd][a]); if (a == b) return a; int i = 19; while (i >= 0) { int na = st[qd][i][a], nb = st[qd][i][b]; if (na != nb) a = na, b = nb; i--; } return st[qd][0][a]; } int n, k, q, t; void dfs3(int x, int par) { if (k > 0) k--, taken[x] = 1; for (int y : g[0][x]) if (y != par) dfs3(y, x); } vector <ar <int, 2>> qrs; void dfs2(int x, int par) { for (int y : g[0][x]) { if (y != par) { if (taken[y]) { cout << "? " << root[0] << ' ' << y << '\n'; qrs.push_back({root[0], y}); } dfs2(y, x); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k >> q >> t; g.assign(2, vector <vector <int>> (n + 1, vector <int>())); st.assign(2, vector <vector <int>> (20, vector <int>(n + 1))); d.assign(2, vector <int>(n + 1)); taken.assign(n + 1, 0); checkpoint.assign(2, vector <int>(n + 1)); for (int i = 0; i < 2; i++) { for (int j = 1; j <= n; j++) { int p; cin >> p; if (~p) g[i][p].emplace_back(j), g[i][j].emplace_back(p); else root[i] = j; } } qd = 0, dfs1(root[0], 0); qd = 1, dfs1(root[1], 0); dfs3(root[0], 0); for (int i = 1; i <= n; i++) if (taken[i]) cout << i << ' '; cout << '\n' << flush; dfs2(root[0], 0); cout << "!\n" << flush; for (int j = 0; j < qrs.size(); j++) { int y = qrs[j][1]; vector <int> res(4); for (int &i : res) cin >> i; qd = 1; int lc = lca(root[0], y); checkpoint[0][y] = res[1]; checkpoint[1][lc] = res[2]; if (lc == root[0]) checkpoint[1][y] = res[3]; else checkpoint[1][y] = res[2] + res[3]; } qd = 1, dfs1(root[0], 0); while (t--) { int a, b; cin >> a >> b; qd = 0; cout << checkpoint[0][a] + checkpoint[0][b] - 2 * checkpoint[0][lca(a, b)] << ' '; qd = 1; cout << checkpoint[1][a] + checkpoint[1][b] - 2 * checkpoint[1][lca(a, b)] << '\n'; } cout << flush; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...