#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 1e6+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;
int n, k, q, t;
int parr[2][maxn];
int root[2];
vector< int > graph[2][maxn];
vector< int > pre[2];
int pos[2][maxn];
int dis[2][maxn];
int dp[2][logo + 10][maxn];
int sol[2][maxn];
bool bio[maxn];
vector< pair<int, int> > edg[2][maxn];
void dfs(int ind, int x, int parr, int d) {
pre[ind].push_back(x);
dis[ind][x] = d;
dp[ind][0][x] = parr;
for (int tren : graph[ind][x]) {
if (tren != parr) dfs(ind, tren, x, d + 1);
}
}
bool cmp(int x, int y) {
return pos[1][x] < pos[1][y];
}
int lif(int ind, int x, int val) {
for (int i = 0; i <= logo; i++) {
if (val & (1 << i)) x = dp[ind][i][x];
}
return x;
}
int lca(int ind, int x, int y) {
if (dis[ind][x] > dis[ind][y]) x = lif(ind, x, dis[ind][x] - dis[ind][y]);
else y = lif(ind, y, dis[ind][y] - dis[ind][x]);
if (x == y) return x;
for (int i = logo; i >= 0; i--) {
if (dp[ind][i][x] != dp[ind][i][y]) {
x = dp[ind][i][x];
y = dp[ind][i][y];
}
}
return dp[ind][0][x];
}
void solve(int ind, int x) {
bio[x] = true;
for (auto iter : edg[ind][x]) {
int tren = iter.X;
int cost = iter.Y;
if (bio[tren]) continue;
sol[ind][tren] = sol[ind][x] + cost;
solve(ind, tren);
}
}
int main() {
scanf("%d%d%d%d", &n, &k, &q, &t);
for (int i = 0; i < 2; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &parr[i][j]);
if (parr[i][j] == -1) root[i] = j;
else graph[i][parr[i][j]].push_back(j);
}
}
dfs(0, root[0], 0, 0); dfs(1, root[1], 1, 0);
for (int p = 0; p < 2; p++)
for (int i = 1; i <= logo; i++)
for (int j = 1; j <= n; j++)
dp[p][i][j] = dp[p][i - 1][dp[p][i - 1][j]];
for (int p = 0; p < 2; p++)
for (int i = 0; i < n; i++)
pos[p][pre[p][i]] = i;
vector< int > v;
for (int i = 1; i <= n; i++) {
if (pos[0][i] < k) v.push_back(i);
}
sort(v.begin(), v.end(), cmp);
assert(v.size() == k);
for (int tren : v) printf("%d ", tren);
printf("\n"); fflush(stdout);
for (int i = 1; i < k; i++) {
printf("? %d %d\n", v[i - 1], v[i]);
}
printf("!\n"); fflush(stdout);
for (int i = 1; i < k; i++) {
int x = v[i - 1], y = v[i];
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
int lcaa = lca(0, x, y);
int lcab = lca(1, x, y);
edg[0][lcaa].push_back({x, a});
edg[0][x].push_back({lcaa, -a});
edg[0][lcaa].push_back({y, b});
edg[0][y].push_back({lcaa, -b});
edg[1][lcab].push_back({x, c});
edg[1][x].push_back({lcab, -c});
edg[1][lcab].push_back({y, d});
edg[1][y].push_back({lcab, -d});
}
memset(bio, false, sizeof bio);
solve(0, v[0]);
memset(bio, false, sizeof bio);
solve(1, v[0]);
while (t--) {
int a, b;
scanf("%d%d", &a, &b);
int lc = lca(0, a, b);
printf("%d ", sol[0][a] + sol[0][b] - 2 * sol[0][lc]);
lc = lca(1, a, b);
printf("%d\n", sol[1][a] + sol[1][b] - 2 * sol[1][lc]);
}
fflush(stdout);
return 0;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from Main.cpp:1:
Main.cpp: In function 'int main()':
Main.cpp:100:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
100 | assert(v.size() == k);
| ~~~~~~~~~^~~~
Main.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d%d%d%d", &n, &k, &q, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:79:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d", &parr[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | scanf("%d %d %d %d", &a, &b, &c, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
663 ms |
266276 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
776 ms |
269124 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
566 ms |
257632 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1244 ms |
421356 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1531 ms |
433440 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
