Submission #1186926

#TimeUsernameProblemLanguageResultExecution timeMemory
1186926elitewantsyouPrize (CEOI22_prize)C++20
10 / 100
2595 ms340772 KiB
#include <bits/stdc++.h> #define ar array using namespace std; const int N = 1e6 + 6; // vector <vector <vector <int>>> g, st; // vector <vector <int>> d; vector <int> g[2][N]; int st[2][20][N], d[2][N]; int root[2], qd; void dfs(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) dfs(y, x); } int lca(int a, int b) { if (d[qd][a] > d[qd][b]) swap(a, b); int i = 0, k = d[qd][b] - d[qd][a]; while (k) { if (k & 1) b = st[qd][i][b]; k >>= 1; i++; } if (a == b) return a; 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 main() { ios::sync_with_stdio(false); cin.tie(0); int n, k, q, t; 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)); vector <int> taken(n + 1), vis(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, dfs(root[0], 0); qd = 1, dfs(root[1], 0); queue <int> que; que.push(root[0]); while (!que.empty()) { int x = que.front(); que.pop(); vis[x] = 1; if (k > 0) k--, taken[x] = 1; for (int y : g[0][x]) if (!vis[y]) que.push(y); } int prnt = 0; for (int i = 1; i <= n; i++) { if (taken[i]) cout << i << " "; } cout << endl; for (int i = 1; i <= n; i++) { if (taken[i] && i != root[0]) { cout << "? " << root[0] << ' ' << i << endl; } } cout << "!" << endl; vector <vector <int>> checkpoint(2, vector <int> (n + 1)); for (int i = 1; i <= n; i++) { if (taken[i] && i != root[0]) { int y = i; 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, dfs(root[0], 0); vector<pair<int, int>> qu(t); for (int i = 0; i < t; i++) { cin >> qu[i].first >> qu[i].second; } for (int i = 0; i < t; i++) { int a = qu[i].first, b = qu[i].second; 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)] << endl; } }
#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...