#include <bits/stdc++.h>
using namespace std;
void massert(bool v) {
if (!v) {
auto start = clock();
int x = 1;
while ((clock() - start) < 5 * CLOCKS_PER_SEC) {
cout << "fuck" << endl;
x <<= 1;
x += 1;
}
}
}
struct Tree {
vector<int> tin, tout, par, depth, jump;
int logn;
void init(vector<vector<int>> adj, int root) {
int n = adj.size();
int T = 0;
tin.assign(n, -1), tout.resize(n), par.resize(n), depth.resize(n), jump.resize(n);
par[root] = jump[root] = root;
function<void(int)> dfs = [&](int v) {
massert(tin[v] == -1);
tin[v] = T++;
for (int to : adj[v]) {
depth[to] = depth[v] + 1;
par[to] = v;
int p = jump[v];
int pp = jump[p];
if (depth[p] - depth[v] == depth[pp] - depth[p]) {
jump[to] = pp;
} else {
jump[to] = v;
}
dfs(to);
}
tout[v] = T;
};
dfs(root);
logn = __lg(n) + 1;
}
bool isp(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (isp(a, b)) {
return a;
}
while (!isp(par.at(a), b)) {
if (isp(jump[a], b)) {
a = par[a];
} else {
a = jump[a];
}
}
return par[a];
}
} t1, t2;
vector<int> normalize(int n, int root, vector<vector<pair<int, int>>> g) {
vector<int> dist(n, -1);
dist[root] = 0;
vector<bool> used(n);
function<void(int)> dfs = [&](int v) {
massert(!used[v]);
used[v] = true;
for (auto [to, w] : g.at(v)) {
massert(to >= 0 && to < n);
if (dist.at(to) == -1) {
dist[to] = dist[v] + w;
dfs(to);
}
}
};
dfs(root);
return dist;
}
int main() {
int n, k, q, t;
cin >> n >> k >> q >> t;
vector<int> p1(n), p2(n);
int root1 = -1, root2 = -1;
for (int i = 0; i < n; ++i) {
cin >> p1[i];
if (p1[i] == -1) {
root1 = i;
} else {
p1[i] -= 1;
}
}
for (int i = 0; i < n; ++i) {
cin >> p2[i];
if (p2[i] == -1) {
root2 = i;
} else {
p2[i] -= 1;
}
}
for (int i = 1; i <= k; ++i) {
cout << i << " \n"[i == k];
}
cout.flush();
assert(max(root1, root2) < n && min(root1, root2) >= 0);
vector<vector<int>> adj(n);
for (int i = 0; i < n; ++i) {
if (p1[i] != -1) {
adj[p1[i]].push_back(i);
}
}
t1.init(adj, root1);
for (int i = 0; i < n; ++i) {
adj[i].clear();
}
for (int i = 0; i < n; ++i) {
if (p2[i] != -1) {
adj[p2[i]].push_back(i);
}
}
t2.init(adj, root2);
vector<pair<int, int>> questions;
vector<int> ord(k);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return t2.tin[i] < t2.tin[j];
});
for (int i = 1; i < ord.size(); ++i) {
questions.emplace_back(ord[i - 1], ord[i]);
}
assert(questions.size() <= q);
for (auto [x, y] : questions) {
cout << "? " << x + 1 << " " << y + 1 << endl;
}
cout << "!" << endl;
vector<vector<pair<int, int>>> g1(n), g2(n);
int h1 = 0, h2 = 0;
auto addEdge = [&](int t, int x, int y, int w) {
if (x == y) {
return;
}
assert(x < n && y < n && x >= 0 && y >= 0);
(t == 0 ? g1[x] : g2[x]).emplace_back(y, w);
(t == 0 ? g1[y] : g2[y]).emplace_back(x, -w);
};
for (auto [x, y] : questions) {
int a, b, c, d;
cin >> a >> b >> c >> d;
int c1 = t1.lca(x, y);
int c2 = t2.lca(x, y);
if (t1.isp(c1, h1)) {
h1 = c1;
}
if (t2.isp(c2, h2)) {
h2 = c2;
}
addEdge(0, c1, x, a);
addEdge(0, c1, y, b);
addEdge(1, c2, x, c);
addEdge(1, c2, y, d);
}
auto first = normalize(n, h1, g1);
auto second = normalize(n, h2, g2);
vector<pair<int, int>> queries(t);
for (auto &[a, b] : queries) {
cin >> a >> b;
a -= 1, b -= 1;
}
for (auto [a, b] : queries) {
int dist1 = first[a] - 2 * first[t1.lca(a, b)] + first[b];
int dist2 = second[a] - 2 * second[t2.lca(a, b)] + second[b];
cout << dist1 << " " << dist2 << '\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:159:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for (int i = 1; i < ord.size(); ++i) {
| ~~^~~~~~~~~~~~
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:163:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
163 | assert(questions.size() <= q);
| ~~~~~~~~~~~~~~~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1299 ms |
149044 KB |
Output is correct |
| 2 |
Correct |
1364 ms |
149080 KB |
Output is correct |
| 3 |
Correct |
1065 ms |
94784 KB |
Output is correct |
| 4 |
Correct |
1014 ms |
93528 KB |
Output is correct |
| 5 |
Correct |
1101 ms |
97496 KB |
Output is correct |
| 6 |
Correct |
1351 ms |
106012 KB |
Output is correct |
| 7 |
Correct |
1325 ms |
106076 KB |
Output is correct |
| 8 |
Correct |
1380 ms |
105076 KB |
Output is correct |
| 9 |
Correct |
1040 ms |
94456 KB |
Output is correct |
| 10 |
Correct |
1066 ms |
96660 KB |
Output is correct |
| 11 |
Correct |
1037 ms |
92264 KB |
Output is correct |
| 12 |
Correct |
1156 ms |
96092 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1431 ms |
147128 KB |
Output is correct |
| 2 |
Correct |
1291 ms |
142792 KB |
Output is correct |
| 3 |
Runtime error |
919 ms |
98784 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
901 ms |
139312 KB |
Output is correct |
| 2 |
Correct |
964 ms |
139256 KB |
Output is correct |
| 3 |
Runtime error |
756 ms |
90952 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2275 ms |
278364 KB |
Output is correct |
| 2 |
Correct |
2214 ms |
278268 KB |
Output is correct |
| 3 |
Runtime error |
1500 ms |
185556 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2633 ms |
284368 KB |
Output is correct |
| 2 |
Correct |
2586 ms |
283856 KB |
Output is correct |
| 3 |
Runtime error |
1816 ms |
185672 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
