#include <bits/stdc++.h>
using namespace std;
void massert(bool f) {
while (!f) {
cout << "hell nah" << endl;
}
}
struct Tree {
vector<int> tin, tout, par;
vector<vector<int>> jump;
int logn;
void init(vector<vector<int>> adj, int root) {
int n = adj.size();
tin.resize(n), tout.resize(n), par.assign(n, -1);
int T = 0;
function<void(int)> dfs = [&](int v) {
tin[v] = T++;
for (int to : adj[v]) {
massert(par[to] == -1);
par[to] = v;
dfs(to);
}
tout[v] = T;
};
dfs(root);
par[root] = root;
logn = __lg(n) + 1;
jump = vector(logn, vector<int>(n));
jump[0] = par;
for (int j = 1; j < logn; ++j) {
for (int i = 0; i < n; ++i) {
jump[j][i] = jump[j - 1][jump[j - 1][i]];
}
}
}
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;
}
for (int i = logn - 1; i >= 0; --i) {
if (!isp(jump[i][a], b)) {
a = jump[i][a];
}
}
return jump[0][a];
}
} t1, t2;
vector<int> normalize(int n, int root, vector<vector<pair<int, int>>> g) {
vector<int> dist(n, -1);
dist[root] = 0;
function<void(int)> dfs = [&](int v) {
for (auto [to, w] : g[v]) {
if (dist[to] == -1) {
dist[to] = dist[v] + w;
massert(dist[to] != -1);
dfs(to);
}
}
};
dfs(root);
return dist;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, q, t;
cin >> n >> k >> q >> t;
vector<int> p1(n), p2(n);
for (int i = 0; i < n; ++i) {
cin >> p1[i];
p1[i] = max(-1, p1[i] - 1);
}
for (int i = 0; i < n; ++i) {
cin >> p2[i];
p2[i] = max(-1, p2[i] - 1);
}
for (int i = 1; i <= k; ++i) {
cout << i << " ";
}
cout << endl;
int root1 = find(p1.begin(), p1.end(), -1) - p1.begin();
int root2 = find(p2.begin(), p2.end(), -1) - p2.begin();
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> any(n, -1);
vector<bool> used(n);
function<void(int)> dfs = [&](int v) {
if (v < k) {
any[v] = v;
}
used[v] = true;
vector<int> alive;
for (int to : adj[v]) {
massert(!used[to]);
dfs(to);
if (any[to] != -1) {
alive.push_back(to);
}
}
if (alive.empty()) {
return;
}
any[v] = any[alive[0]];
if (alive.size() == 1) {
if (v < k) {
questions.emplace_back(any[alive[0]], v);
}
} else {
for (int i = 1; i < alive.size(); ++i) {
questions.emplace_back(any[alive[0]], any[alive[i]]);
}
}
};
dfs(root2);
for (auto [x, y] : questions) {
cout << "? " << x + 1 << " " << y + 1 << endl;
}
cout << "!" << endl;
vector<vector<pair<int, int>>> g1(n), g2(n);
int h1 = -1, h2 = -1;
auto addEdge = [&](int t, int x, int y, int w) {
(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 (h1 == -1 || t1.isp(c1, h1)) {
h1 = c1;
}
if (h2 == -1 || 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] + first[b] - 2 * first[t1.lca(a, b)];
int dist2 = second[a] + second[b] - 2 * second[t2.lca(a, b)];
cout << dist1 << " " << dist2 << '\n';
}
return 0;
}
Compilation message
Main.cpp: In lambda function:
Main.cpp:167:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for (int i = 1; i < alive.size(); ++i) {
| ~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1604 ms |
217668 KB |
Output is correct |
| 2 |
Correct |
1560 ms |
221532 KB |
Output is correct |
| 3 |
Correct |
1348 ms |
163560 KB |
Output is correct |
| 4 |
Correct |
1243 ms |
162972 KB |
Output is correct |
| 5 |
Correct |
1395 ms |
167256 KB |
Output is correct |
| 6 |
Correct |
1736 ms |
176136 KB |
Output is correct |
| 7 |
Correct |
1735 ms |
176044 KB |
Output is correct |
| 8 |
Correct |
1592 ms |
174904 KB |
Output is correct |
| 9 |
Correct |
1120 ms |
163304 KB |
Output is correct |
| 10 |
Correct |
1279 ms |
166236 KB |
Output is correct |
| 11 |
Correct |
1127 ms |
161312 KB |
Output is correct |
| 12 |
Correct |
1197 ms |
165616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1609 ms |
220732 KB |
Output is correct |
| 2 |
Correct |
1445 ms |
214216 KB |
Output is correct |
| 3 |
Runtime error |
846 ms |
167384 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
977 ms |
207928 KB |
Output is correct |
| 2 |
Correct |
972 ms |
207924 KB |
Output is correct |
| 3 |
Runtime error |
560 ms |
159724 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2250 ms |
423172 KB |
Output is correct |
| 2 |
Correct |
2284 ms |
423072 KB |
Output is correct |
| 3 |
Runtime error |
1247 ms |
330324 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2696 ms |
434688 KB |
Output is correct |
| 2 |
Correct |
2644 ms |
434260 KB |
Output is correct |
| 3 |
Runtime error |
1570 ms |
330572 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
