#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18;
const int LOG = 18;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, S, Q, E;
cin >> N >> S >> Q >> E;
E--;
vector<pair<int, int>> edges;
vector<vector<pair<int, int>>> adj(N);
for (int i = 1; i < N; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
edges.emplace_back(u, v);
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
vector<int> depth(N);
vector<lint> dp(N, INF);
vector<lint> dist(N, 0);
vector<vector<int>> par(LOG, vector<int>(N, -1));
vector<vector<lint>> lift(LOG, vector<lint>(N, INF));
for (int i = 0; i < S; i++) {
int x;
cin >> x;
dp[--x] = 0;
}
const auto Dfs = [&](const auto &self, int u, int p) -> void {
par[0][u] = p;
vector<pair<lint, int>> ls;
ls.emplace_back(dp[u], u);
for (auto [v, w] : adj[u]) if (v != p) {
dist[v] = dist[u] + w;
depth[v] = depth[u] + 1;
self(self, v, u);
ls.emplace_back(dp[v] + w, v);
dp[u] = min(dp[u], dp[v] + w);
}
sort(begin(ls), end(ls));
for (auto [v, w] : adj[u]) if (v != p) {
lift[0][v] = (ls[0].second == v ? ls[1].first : ls[0].first) - dist[u];
}
};
Dfs(Dfs, E, -1);
for (int j = 1; j < LOG; j++) {
for (int u = 0; u < N; u++) {
par[j][u] = par[j - 1][u];
lift[j][u] = lift[j - 1][u];
if (par[j - 1][u] != -1) {
par[j][u] = par[j - 1][par[j - 1][u]];
lift[j][u] = min(lift[j][u], lift[j - 1][par[j - 1][u]]);
}
}
}
const auto IsAncestor = [&](int x, int y) -> bool { // is x ancestor of y?
if (depth[x] > depth[y]) return false;
int d = depth[y] - depth[x];
for (int i = 0; i < LOG; i++) {
if ((d >> i) & 1) {
y = par[i][y];
}
}
return x == y;
};
const auto GetMinCost = [&](int u, int d) -> lint {
if (d < 0) return INF;
lint ans = INF;
for (int i = 0; i < LOG; i++) {
if ((d >> i) & 1) {
ans = min(ans, lift[i][u]);
u = par[i][u];
}
}
ans = min(ans, lift[0][u]);
return ans;
};
while (Q--) {
int i, r;
cin >> i >> r;
i--, r--;
if (IsAncestor(edges[i].first, r) && IsAncestor(edges[i].second, r)) {
int d = depth[r] - max(depth[edges[i].first], depth[edges[i].second]);
lint ans = min(dp[r], dist[r] + GetMinCost(r, d - 1));
if (ans > (INF / 100)) {
cout << "oo\n";
} else {
cout << ans << '\n';
}
} else {
cout << "escaped\n";
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
460 KB |
Output is correct |
2 |
Correct |
4 ms |
460 KB |
Output is correct |
3 |
Correct |
4 ms |
460 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
460 KB |
Output is correct |
2 |
Correct |
4 ms |
460 KB |
Output is correct |
3 |
Correct |
4 ms |
460 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
2 ms |
588 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
588 KB |
Output is correct |
10 |
Correct |
2 ms |
588 KB |
Output is correct |
11 |
Correct |
2 ms |
588 KB |
Output is correct |
12 |
Correct |
2 ms |
588 KB |
Output is correct |
13 |
Correct |
2 ms |
588 KB |
Output is correct |
14 |
Correct |
3 ms |
588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
169 ms |
35376 KB |
Output is correct |
2 |
Correct |
168 ms |
35068 KB |
Output is correct |
3 |
Correct |
180 ms |
35020 KB |
Output is correct |
4 |
Correct |
214 ms |
39352 KB |
Output is correct |
5 |
Correct |
198 ms |
39300 KB |
Output is correct |
6 |
Correct |
296 ms |
44876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
460 KB |
Output is correct |
2 |
Correct |
4 ms |
460 KB |
Output is correct |
3 |
Correct |
4 ms |
460 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
2 ms |
588 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
2 ms |
588 KB |
Output is correct |
10 |
Correct |
2 ms |
588 KB |
Output is correct |
11 |
Correct |
2 ms |
588 KB |
Output is correct |
12 |
Correct |
2 ms |
588 KB |
Output is correct |
13 |
Correct |
2 ms |
588 KB |
Output is correct |
14 |
Correct |
3 ms |
588 KB |
Output is correct |
15 |
Correct |
169 ms |
35376 KB |
Output is correct |
16 |
Correct |
168 ms |
35068 KB |
Output is correct |
17 |
Correct |
180 ms |
35020 KB |
Output is correct |
18 |
Correct |
214 ms |
39352 KB |
Output is correct |
19 |
Correct |
198 ms |
39300 KB |
Output is correct |
20 |
Correct |
296 ms |
44876 KB |
Output is correct |
21 |
Correct |
145 ms |
34980 KB |
Output is correct |
22 |
Correct |
149 ms |
34524 KB |
Output is correct |
23 |
Correct |
189 ms |
34504 KB |
Output is correct |
24 |
Correct |
203 ms |
39508 KB |
Output is correct |
25 |
Correct |
247 ms |
46504 KB |
Output is correct |
26 |
Correct |
137 ms |
34912 KB |
Output is correct |
27 |
Correct |
150 ms |
34532 KB |
Output is correct |
28 |
Correct |
162 ms |
34512 KB |
Output is correct |
29 |
Correct |
199 ms |
37536 KB |
Output is correct |
30 |
Correct |
244 ms |
41160 KB |
Output is correct |
31 |
Correct |
172 ms |
34896 KB |
Output is correct |
32 |
Correct |
159 ms |
34540 KB |
Output is correct |
33 |
Correct |
176 ms |
34648 KB |
Output is correct |
34 |
Correct |
258 ms |
39080 KB |
Output is correct |
35 |
Correct |
235 ms |
46200 KB |
Output is correct |
36 |
Correct |
192 ms |
39296 KB |
Output is correct |