제출 #1187397

#제출 시각아이디문제언어결과실행 시간메모리
1187397user192837Prize (CEOI22_prize)C++17
10 / 100
2940 ms301464 KiB
#include <bits/stdc++.h> #define ar array using namespace std; typedef long long ll; const int N = 1e6 + 6; vector <int> g[2][N]; ll checkpoint[2][N]; int st[2][20][N], d[2][N], taken[N], vis[N], root[2], qd; void dfs(int x1, int par1) { stack <ar <int, 2>> s; s.push({x1, par1}); while (!s.empty()) { auto now = s.top(); s.pop(); int x = now[0], par = now[1]; 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) s.push({y, x}); } } int mx = -1, mn = 1e9; int lca(int a, int b) { mx = max(mx, max(a, b)); mn = min(mn, min(a, b)); while (max(a, b) >= N || min(a, b) < 1) cout << "cout\n" << flush; 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); cout.tie(0); int n, k, q, t; cin >> n >> k >> q >> t; 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]) { if (prnt) cout << ' '; cout << i, prnt = 1; } } cout << '\n' << flush; for (int i = 1; i <= n; i++) { if (taken[i] && i != root[0]) { cout << "? " << root[0] << ' ' << i << '\n'; q--; } } cout << "!\n" << flush; for (int i = 1; i <= n; i++) { if (taken[i] && i != root[0]) { int y = i; vector <ll> res(4); for (ll &j : res) cin >> j; 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 <ar <int, 2>> qrs(t); for (auto &i : qrs) cin >> i[0] >> i[1]; for (auto i : qrs) { int a = i[0], b = i[1]; 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...