#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |