#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAX = 1050000;
int n, k, q, t, r1, r2;
int a[MAX], b[MAX], c[MAX], d[MAX];
vector<int> ids;
namespace tree1 {
int dep[MAX], logs[2 * MAX], p[MAX];
pair<int, int> st[2 * MAX][20];
vector<int> gph[MAX];
vector<pi> adj[MAX];
vector<pair<int, int>> euler;
int dist[MAX];
bool seen[MAX];
void add(int u, int v) {
gph[u].push_back(v);
gph[v].push_back(u);
}
void dfs(int x, int px) {
if (sz(ids) < k) {
ids.push_back(x);
}
dep[x] = dep[px] + 1;
p[x] = sz(euler);
euler.push_back({dep[x], x});
for (auto& y : gph[x]) {
if (y == px) continue;
dfs(y, x);
euler.push_back({dep[x], x});
}
}
int getlca(int s, int e) {
if (p[s] > p[e]) swap(s, e);
int k = logs[p[e] - p[s] + 1];
return min(st[p[s]][k], st[p[e] - (1 << k) + 1][k]).second;
}
void dfs(int x) {
seen[x] = true;
for (auto& y : adj[x]) {
if (seen[y[0]]) continue;
dist[y[0]] = dist[x] + y[1];
dfs(y[0]);
}
}
void build() {
for (int i = 2; i < 2 * MAX; i++)
logs[i] = logs[i >> 1] + 1;
for (int i = 0; i < sz(euler); i++)
st[i][0] = euler[i];
for (int j = 1; j < 20; j++)
for (int i = 0; i + (1 << j) <= sz(euler); i++)
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
for (int i = 0; i + 1 < k; i++) {
int x = ids[i];
int y = ids[i + 1];
int z = getlca(ids[i], ids[i + 1]);
adj[x].push_back({z, -a[i]});
adj[z].push_back({x, a[i]});
adj[y].push_back({z, -b[i]});
adj[z].push_back({y, b[i]});
}
dfs(r1);
}
int query(int x, int y) {
return dist[x] + dist[y] - 2 * dist[getlca(x, y)];
}
};
namespace tree2 {
int dfn[MAX], T, dep[MAX], p[MAX], logs[2 * MAX];
vector<pair<int, int>> euler;
pair<int, int> st[2 * MAX][20];
vector<int> gph[MAX];
vector<pi> adj[MAX];
int dist[MAX];
bool seen[MAX];
void add(int u, int v) {
gph[u].push_back(v);
gph[v].push_back(u);
}
void dfs(int x, int px) {
dfn[x] = ++T;
dep[x] = dep[px] + 1;
p[x] = sz(euler);
euler.push_back({dep[x], x});
for (auto& y : gph[x]) {
if (y == px) continue;
dfs(y, x);
euler.push_back({dep[x], x});
}
}
int getlca(int s, int e) {
if (p[s] > p[e]) swap(s, e);
int k = logs[p[e] - p[s] + 1];
return min(st[p[s]][k], st[p[e] - (1 << k) + 1][k]).second;
}
void order() {
sort(all(ids), [&](int i, int j) { return dfn[i] < dfn[j]; });
}
void dfs(int x) {
seen[x] = true;
for (auto& y : adj[x]) {
if (seen[y[0]]) continue;
dist[y[0]] = dist[x] + y[1];
dfs(y[0]);
}
}
void build() {
for (int i = 2; i < 2 * MAX; i++)
logs[i] = logs[i >> 1] + 1;
for (int i = 0; i < sz(euler); i++)
st[i][0] = euler[i];
for (int j = 1; j < 20; j++)
for (int i = 0; i + (1 << j) <= sz(euler); i++)
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
for (int i = 0; i + 1 < k; i++) {
int x = ids[i];
int y = ids[i + 1];
int z = getlca(ids[i], ids[i + 1]);
adj[x].push_back({z, -c[i]});
adj[z].push_back({x, c[i]});
adj[y].push_back({z, -d[i]});
adj[z].push_back({y, d[i]});
}
vector<int> ord(n);
iota(all(ord), 0);
sort(all(ord), [&](int i, int j) { return dfn[i] < dfn[j]; });
for (int x : ord) if (!seen[x]) dfs(x);
}
int query(int x, int y) {
return dist[x] + dist[y] - 2 * dist[getlca(x, y)];
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k >> q >> t;
for (int i = 0; i < n; i++) {
int p;
cin >> p;
if (p == -1) {
r1 = i;
} else {
--p;
tree1::add(i, p);
}
}
for (int i = 0; i < n; i++) {
int p;
cin >> p;
if (p == -1) {
r2 = i;
} else {
--p;
tree2::add(i, p);
}
}
tree1::dfs(r1, r1);
tree2::dfs(r2, r2);
tree2::order();
for (int i = 0; i < k; i++) {
cout << ids[i] + 1 << " ";
}
cout << "\n";
for (int i = 0; i + 1 < k; i++) {
cout << "? " << ids[i] + 1 << " " << ids[i + 1] + 1 << "\n";
}
cout << "!" << endl;
for (int i = 0; i + 1 < k; i++) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
}
tree1::build();
tree2::build();
vector<int> x(t), y(t);
for (int i = 0; i < t; i++) {
cin >> x[i] >> y[i];
--x[i]; --y[i];
}
for (int i = 0; i < t; i++) {
cout << tree1::query(x[i], y[i]) << " " << tree2::query(x[i], y[i]) << "\n";
}
cout << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1669 ms |
567800 KB |
Output is correct |
2 |
Correct |
1654 ms |
571524 KB |
Output is correct |
3 |
Correct |
1575 ms |
524648 KB |
Output is correct |
4 |
Correct |
1544 ms |
524676 KB |
Output is correct |
5 |
Correct |
1596 ms |
526580 KB |
Output is correct |
6 |
Correct |
1777 ms |
533372 KB |
Output is correct |
7 |
Correct |
1695 ms |
534112 KB |
Output is correct |
8 |
Correct |
1652 ms |
528888 KB |
Output is correct |
9 |
Correct |
1568 ms |
523452 KB |
Output is correct |
10 |
Correct |
1608 ms |
526604 KB |
Output is correct |
11 |
Correct |
1504 ms |
520216 KB |
Output is correct |
12 |
Correct |
1561 ms |
524004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1799 ms |
571912 KB |
Output is correct |
2 |
Correct |
1679 ms |
568952 KB |
Output is correct |
3 |
Correct |
1588 ms |
523308 KB |
Output is correct |
4 |
Correct |
1628 ms |
526648 KB |
Output is correct |
5 |
Correct |
1594 ms |
526436 KB |
Output is correct |
6 |
Correct |
1695 ms |
530252 KB |
Output is correct |
7 |
Correct |
1756 ms |
534668 KB |
Output is correct |
8 |
Correct |
1784 ms |
534204 KB |
Output is correct |
9 |
Correct |
1750 ms |
536512 KB |
Output is correct |
10 |
Correct |
1664 ms |
535840 KB |
Output is correct |
11 |
Correct |
1630 ms |
531988 KB |
Output is correct |
12 |
Correct |
1710 ms |
533476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1452 ms |
560948 KB |
Output is correct |
2 |
Correct |
1412 ms |
559376 KB |
Output is correct |
3 |
Correct |
1274 ms |
515700 KB |
Output is correct |
4 |
Correct |
1272 ms |
514536 KB |
Output is correct |
5 |
Correct |
1217 ms |
513336 KB |
Output is correct |
6 |
Correct |
1326 ms |
523144 KB |
Output is correct |
7 |
Correct |
1379 ms |
522016 KB |
Output is correct |
8 |
Correct |
1360 ms |
519636 KB |
Output is correct |
9 |
Correct |
1369 ms |
523380 KB |
Output is correct |
10 |
Correct |
1283 ms |
523988 KB |
Output is correct |
11 |
Correct |
1275 ms |
521204 KB |
Output is correct |
12 |
Correct |
1273 ms |
522304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3234 ms |
975372 KB |
Output is correct |
2 |
Correct |
3253 ms |
976808 KB |
Output is correct |
3 |
Runtime error |
2702 ms |
883448 KB |
Execution killed with signal 13 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3528 ms |
987056 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |