#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;
pair<int, int> roads[100000];
vector<pair<int, int>> graph[100001];
bool is_shop[100001];
int tin[100001], tout[100001], level[100001], indx = 0;
pair<int, ll> bl[100001][20]; // Binary Lifting
ll dp1[100001], dp2[100001][20];
void dfs(int node, int parent = 0, int depth = 0) {
tin[node] = indx++;
level[node] = depth;
dp1[node] = (is_shop[node] ? 0 : 1ll << 60);
FOR(i, 1, 20) {
bl[node][i] = {
bl[bl[node][i - 1].first][i - 1].first,
bl[node][i - 1].second + bl[bl[node][i - 1].first][i - 1].second};
}
for (auto& i : graph[node]) {
if (i.first != parent) {
bl[i.first][0] = {node, i.second};
dfs(i.first, node, depth + 1);
dp1[node] = min(dp1[node], dp1[i.first] + i.second);
}
}
tout[node] = indx++;
}
void dfs2(int node, int parent = 0, int dist = 0) {
dp2[node][0] = dp1[parent] + dist;
FOR(i, 1, 20) {
dp2[node][i] = min(dp2[node][i - 1], dp2[bl[node][i - 1].first][i - 1] +
bl[node][i - 1].second);
}
for (auto& i : graph[node]) {
if (i.first != parent) dfs2(i.first, node, i.second);
}
}
bool is_ancestor(int u, int v) {
return (tin[u] >= tin[v] && tout[u] <= tout[v]);
}
int main() {
iostream::sync_with_stdio(false);
cin.tie(0);
int n, s, q, e;
cin >> n >> s >> q >> e;
FOR(i, 1, n) {
int a, b, w;
cin >> a >> b >> w;
graph[a].push_back({b, w});
graph[b].push_back({a, w});
roads[i] = {a, b};
}
FOR(i, 0, s) {
int x;
cin >> x;
is_shop[x] = true;
}
dfs(e);
dfs2(e);
while (q--) {
int i, r;
cin >> i >> r;
if (is_ancestor(r, roads[i].first) && is_ancestor(r, roads[i].second)) {
if (tin[roads[i].first] < tin[roads[i].second])
swap(roads[i].first, roads[i].second);
int dist = level[r] - level[roads[i].first];
ll ans = dp1[r];
ll len = 0;
int pw = 0;
while (dist) {
if (dist & 1) {
ans = min(ans, len + dp2[r][pw]);
len += bl[r][pw].second;
r = bl[r][pw].first;
}
dist >>= 1;
pw++;
}
if (ans == 1ll << 60)
cout << "oo\n";
else
cout << ans << '\n';
} else
cout << "escaped\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2808 KB |
Output is correct |
2 |
Correct |
6 ms |
2808 KB |
Output is correct |
3 |
Correct |
6 ms |
2808 KB |
Output is correct |
4 |
Correct |
6 ms |
2812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2808 KB |
Output is correct |
2 |
Correct |
6 ms |
2808 KB |
Output is correct |
3 |
Correct |
6 ms |
2808 KB |
Output is correct |
4 |
Correct |
6 ms |
2812 KB |
Output is correct |
5 |
Correct |
6 ms |
3320 KB |
Output is correct |
6 |
Correct |
5 ms |
3320 KB |
Output is correct |
7 |
Correct |
5 ms |
3320 KB |
Output is correct |
8 |
Correct |
5 ms |
3064 KB |
Output is correct |
9 |
Correct |
5 ms |
3292 KB |
Output is correct |
10 |
Correct |
6 ms |
3320 KB |
Output is correct |
11 |
Correct |
6 ms |
3192 KB |
Output is correct |
12 |
Correct |
6 ms |
3448 KB |
Output is correct |
13 |
Correct |
6 ms |
3320 KB |
Output is correct |
14 |
Correct |
7 ms |
3320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
226 ms |
57120 KB |
Output is correct |
2 |
Correct |
237 ms |
56604 KB |
Output is correct |
3 |
Correct |
243 ms |
56672 KB |
Output is correct |
4 |
Correct |
277 ms |
58108 KB |
Output is correct |
5 |
Correct |
263 ms |
58232 KB |
Output is correct |
6 |
Correct |
316 ms |
59732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2808 KB |
Output is correct |
2 |
Correct |
6 ms |
2808 KB |
Output is correct |
3 |
Correct |
6 ms |
2808 KB |
Output is correct |
4 |
Correct |
6 ms |
2812 KB |
Output is correct |
5 |
Correct |
6 ms |
3320 KB |
Output is correct |
6 |
Correct |
5 ms |
3320 KB |
Output is correct |
7 |
Correct |
5 ms |
3320 KB |
Output is correct |
8 |
Correct |
5 ms |
3064 KB |
Output is correct |
9 |
Correct |
5 ms |
3292 KB |
Output is correct |
10 |
Correct |
6 ms |
3320 KB |
Output is correct |
11 |
Correct |
6 ms |
3192 KB |
Output is correct |
12 |
Correct |
6 ms |
3448 KB |
Output is correct |
13 |
Correct |
6 ms |
3320 KB |
Output is correct |
14 |
Correct |
7 ms |
3320 KB |
Output is correct |
15 |
Correct |
226 ms |
57120 KB |
Output is correct |
16 |
Correct |
237 ms |
56604 KB |
Output is correct |
17 |
Correct |
243 ms |
56672 KB |
Output is correct |
18 |
Correct |
277 ms |
58108 KB |
Output is correct |
19 |
Correct |
263 ms |
58232 KB |
Output is correct |
20 |
Correct |
316 ms |
59732 KB |
Output is correct |
21 |
Correct |
220 ms |
57068 KB |
Output is correct |
22 |
Correct |
229 ms |
56668 KB |
Output is correct |
23 |
Correct |
240 ms |
56696 KB |
Output is correct |
24 |
Correct |
260 ms |
58440 KB |
Output is correct |
25 |
Correct |
323 ms |
60664 KB |
Output is correct |
26 |
Correct |
218 ms |
57376 KB |
Output is correct |
27 |
Correct |
228 ms |
56824 KB |
Output is correct |
28 |
Correct |
243 ms |
56948 KB |
Output is correct |
29 |
Correct |
258 ms |
57860 KB |
Output is correct |
30 |
Correct |
288 ms |
59028 KB |
Output is correct |
31 |
Correct |
209 ms |
57108 KB |
Output is correct |
32 |
Correct |
229 ms |
56824 KB |
Output is correct |
33 |
Correct |
257 ms |
56928 KB |
Output is correct |
34 |
Correct |
271 ms |
58232 KB |
Output is correct |
35 |
Correct |
296 ms |
60420 KB |
Output is correct |
36 |
Correct |
265 ms |
58928 KB |
Output is correct |