#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "../../debug.h"
#else
#define debug(...) void(23)
#endif
constexpr int max_N = int(1E6) + 5;
constexpr int LG = 20;
int N, K, Q, T;
int root[2], par[2][LG][max_N], tin[2][max_N], tout[2][max_N], timer;
std::vector<int> adj[2][max_N];
std::vector<int> vec;
void dfs(int tp, int v) {
tin[tp][v] = timer++;
if (vec.size() < K) {
vec.emplace_back(v);
}
for (auto u : adj[tp][v]) {
par[tp][0][u] = v;
dfs(tp, u);
}
tout[tp][v] = timer;
}
bool is_in_subtree(int tp, int u, int v) {
return tin[tp][v] <= tin[tp][u] && tout[tp][u] <= tout[tp][v];
}
int lca(int tp, int u, int v) {
if (is_in_subtree(tp, u, v)) {
return v;
} else if (is_in_subtree(tp, v, u)) {
return u;
}
for (int lg = LG - 1; lg >= 0; --lg) {
if (!is_in_subtree(tp, v, par[tp][lg][u])) {
u = par[tp][lg][u];
}
}
return par[tp][0][u];
}
int dep[2][max_N], vis[2][max_N];
std::vector<std::pair<int, int>> hint[2][max_N];
void add_edge(int tp, int u, int v, int x) {
hint[tp][v].emplace_back(u, x);
hint[tp][u].emplace_back(v, -x);
}
void solve(int tp, int v) {
vis[tp][v] = true;
debug(tp, v, dep[tp][v]);
for (auto[u, w] : hint[tp][v]) {
if (vis[tp][u]) {
if(dep[tp][u] != dep[tp][v] + w) {
debug(tp, u, v, w, dep[tp][u], dep[tp][v]);
assert(false);
}
continue;
}
dep[tp][u] = dep[tp][v] + w;
solve(tp, u);
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> N >> K >> Q >> T;
for (int tp : {0, 1}) {
for (int i = 0; i < N; ++i) {
int P;
std::cin >> P;
if (P == -1) {
root[tp] = i;
} else {
adj[tp][P - 1].emplace_back(i);
}
}
}
timer = 0;
dfs(0, root[0]);
timer = 0;
dfs(1, root[1]);
for (int tp : {0, 1}) {
par[tp][0][root[tp]] = root[tp];
for (int lg = 0; lg + 1 < LG; ++lg) {
for (int i = 0; i < N; ++i) {
par[tp][lg + 1][i] = par[tp][lg][par[tp][lg][i]];
}
}
}
std::sort(vec.begin(), vec.end(), [&](auto lhs, auto rhs) {
return tin[1][lhs] < tin[1][rhs];
});
for (int i = 0; i < K; ++i) {
std::cout << vec[i] + 1 << " "[i == K - 1];
}
std::cout.flush();
for (int i = 0; i < K - 1; ++i) {
std::cout << "? " << vec[i] + 1 << ' ' << vec[i + 1] + 1 << '\n';
}
std::cout << "!\n";
std::cout.flush();
for (int i = 0; i < K - 1; ++i) {
int A, B, C, D;
std::cin >> A >> B >> C >> D;
int u = vec[i], v = vec[i + 1];
int lca0 = lca(0, u, v);
int lca1 = lca(1, u, v);
add_edge(0, u, lca0, A);
add_edge(0, v, lca0, B);
add_edge(1, u, lca1, C);
add_edge(1, v, lca1, D);
}
solve(0, vec[0]);
solve(1, vec[0]);
for (int i = 0; i < T; ++i) {
int A, B;
std::cin >> A >> B;
--A, --B;
int lca0 = lca(0, A, B);
int lca1 = lca(1, A, B);
int ans0 = dep[0][A] + dep[0][B] - 2 * dep[0][lca0];
int ans1 = dep[1][A] + dep[1][B] - 2 * dep[1][lca1];
std::cout << ans0 << ' ' << ans1 << '\n';
std::cout.flush();
}
return 0;
}
Compilation message
Main.cpp: In function 'void dfs(int, int)':
Main.cpp:21:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
21 | if (vec.size() < K) {
| ~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
444 ms |
338084 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
528 ms |
338372 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
902 ms |
684580 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1569 ms |
832900 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
993 ms |
409204 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
