#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(v) begin(v), end(v)
using namespace std;
using ll = long long;
template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }
class LowestCommonAncestor {
const vector<vector<int>>& G;
vector<int> dep;
vector<vector<int>> par;
void dfs(int v, int p) {
par[0][v] = p;
for (int u : G[v]) {
if (u == p) continue;
dep[u] = dep[v] + 1;
dfs(u, v);
}
}
public:
LowestCommonAncestor(const vector<vector<int>>& G_, int r) : G(G_) {
int N = G.size();
dep.assign(N, 0);
par.assign(22, vector<int>(N, -1));
dfs(r, -1);
rep (i, 21) rep (v, N) {
par[i + 1][v] = par[i][v] == -1 ? -1 : par[i][par[i][v]];
}
}
int lca(int a, int b) const {
if (dep[a] > dep[b]) swap(a, b);
rrep (i, 22) {
if ((dep[b] - dep[a]) >> i & 1) b = par[i][b];
}
if (a == b) return a;
rrep (i, 22) {
if (par[i][a] != par[i][b]) {
a = par[i][a];
b = par[i][b];
}
}
return par[0][a];
}
int depth(int v) const { return dep[v]; }
};
class WeightedUnionFind {
vector<int> par, wei;
public:
WeightedUnionFind(int n) : par(n, -1), wei(n, 0) {}
int find(int v) {
if (par[v] < 0) return v;
int r = find(par[v]);
wei[v] += wei[par[v]];
return par[v] = r;
}
int weight(int v) {
find(v);
return wei[v];
}
void merge(int u, int v, int w) {
w += weight(u);
w -= weight(v);
u = find(u);
v = find(v);
if (u == v) {
assert(w == 0);
return;
}
par[u] += par[v];
par[v] = u;
wei[v] = w;
}
};
int main() {
int N, K, Q, T; cin >> N >> K >> Q >> T;
vector<int> P1(N), P2(N);
int r1 = -1, r2 = -1;
vector<vector<int>> G1(N), G2(N);
rep (i, N) {
cin >> P1[i];
if (P1[i] == -1) r1 = i;
else G1[--P1[i]].push_back(i);
}
rep (i, N) {
cin >> P2[i];
if (P2[i] == -1) r2 = i;
else G2[--P2[i]].push_back(i);
}
vector<int> verts;
{
auto dfs = [&](auto&& self, int v) -> void {
if ((int)verts.size() == K) return;
verts.push_back(v);
for (int u : G1[v]) self(self, u);
};
dfs(dfs, r1);
}
int raux;
vector<int> aux;
vector<int> Paux(N, -1);
vector<vector<int>> Gaux(N);
{
// G2 における verts の auxiliary tree を作る
vector<int> ord(N);
{
int cnt = 0;
auto dfs = [&](auto&& self, int v) -> void {
ord[v] = cnt++;
for (int u : G2[v]) self(self, u);
};
dfs(dfs, r2);
}
LowestCommonAncestor lca(G2, r2);
sort(all(verts), [&](int a, int b) { return ord[a] < ord[b]; });
for (auto i : verts) {
aux.push_back(i);
}
rep (i, K - 1) {
aux.push_back(lca.lca(verts[i], verts[i + 1]));
}
sort(all(aux), [&](int a, int b) { return ord[a] < ord[b]; });
aux.erase(unique(all(aux)), aux.end());
raux = aux.front();
stack<int> st;
for (int v : aux) {
if (st.empty()) {
st.push(v);
continue;
}
while (lca.lca(st.top(), v) != st.top()) st.pop();
Gaux[st.top()].push_back(v);
Paux[v] = st.top();
st.push(v);
}
}
vector<int> is_aux(N, -1);
for (auto v : aux) is_aux[v] = 0;
for (auto v : verts) is_aux[v] = 1;
rep (i, K) cout << verts[i] + 1 << " \n"[i == K - 1];
vector<pair<int, int>> qs;
{
auto dfs = [&](auto&& self, int v) -> int {
int res = -1;
if (is_aux[v] == 1) res = v;
for (int u : Gaux[v]) {
int r = self(self, u);
if (res == -1) res = r;
else {
qs.emplace_back(res, r);
}
}
return res;
};
dfs(dfs, raux);
}
assert((int)qs.size() == K - 1);
for (auto [a, b] : qs) cout << "? " << a + 1 << " " << b + 1 << "\n";
cout << "!" << endl;
LowestCommonAncestor lca1(G1, r1), lca2(G2, r2);
WeightedUnionFind uf1(N), uf2(N);
rep (i, qs.size()) {
auto [a, b] = qs[i];
int d1a, d1b, d2a, d2b; cin >> d1a >> d1b >> d2a >> d2b;
int l1 = lca1.lca(a, b), l2 = lca2.lca(a, b);
uf1.merge(l1, a, d1a); uf1.merge(l1, b, d1b);
uf2.merge(l2, a, d2a); uf2.merge(l2, b, d2b);
}
rep (_, T) {
int a, b; cin >> a >> b; --a; --b;
int l1 = lca1.lca(a, b), l2 = lca2.lca(a, b);
int d1 = uf1.weight(a) + uf1.weight(b) - 2 * uf1.weight(l1);
int d2 = uf2.weight(a) + uf2.weight(b) - 2 * uf2.weight(l2);
cout << d1 << " " << d2 << "\n";
}
cout << flush;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
795 ms |
192224 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1014 ms |
194212 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
642 ms |
188368 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1795 ms |
376080 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2158 ms |
382020 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
