#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 200005;
const int INF = 1LL << 60;
int n, s, q, e;
vector<pair<int,int>> adj[maxn];
pair<int,int> edges[maxn];
int dist[maxn];
int dpth[maxn];
int closest[maxn];
int shop[maxn];
int bl[maxn][20];
int bld[maxn][20];
int st[maxn], en[maxn], cur = 0;
void dfs(int nd, int par, int d) {
st[nd] = cur++;
dist[nd] = dist[par] + d;
dpth[nd] = dpth[par] + 1;
for (auto i : adj[nd])
if (i.first != par)
dfs(i.first, nd, i.second);
closest[nd] = (shop[nd] ? dist[nd] : INF);
for (auto i : adj[nd])
if (i.first != par && closest[i.first] != INF)
closest[nd] = min(closest[nd], closest[i.first]);
en[nd] = cur++;
}
void dfs_bl(int nd, int par) {
bl[nd][0] = par;
bld[nd][0] = (closest[nd] == INF ? INF : closest[nd] - 2 * dist[nd]);
for (int i = 1; i < 20; i++) bl[nd][i] = bl[bl[nd][i-1]][i-1];
for (int i = 1; i < 20; i++) bld[nd][i] = min(bld[nd][i-1], bld[bl[nd][i-1]][i-1]);
for (auto i : adj[nd])
if (i.first != par)
dfs_bl(i.first, nd);
}
signed main() {
cin >> n >> s >> q >> e; e--;
for (int i = 0; i < n-1; i++) {
int a, b, c; cin >> a >> b >> c; a--, b--;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
edges[i] = make_pair(a, b);
}
for (int i = 0; i < s; i++) {
int a; cin >> a; a--;
shop[a] = 1;
}
dfs(e, e, 0);
dfs_bl(e, e);
for (int i = 0; i < n-1; i++)
if (dpth[edges[i].first] < dpth[edges[i].second])
swap(edges[i].first, edges[i].second);
for (int i = 0; i < q; i++) {
int a, b; cin >> a >> b; a--, b--;
// can escape?
if (!(st[edges[a].first] <= st[b] && en[b] <= en[edges[a].first])) {
cout << "escaped" << endl;
continue;
}
int cost = INF;
int nd = b;
for (int i = 19; i >= 0; i--)
if (((dpth[b] - dpth[edges[a].first]) >> i) & 1)
cost = min(cost, bld[nd][i]),
nd = bl[nd][i];
cost = min(cost, bld[nd][0]);
if (cost == INF) { cout << "oo" << endl; continue; }
cout << cost + dist[b] << endl;
continue;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
5132 KB |
Output is correct |
2 |
Correct |
15 ms |
5076 KB |
Output is correct |
3 |
Correct |
19 ms |
5164 KB |
Output is correct |
4 |
Correct |
16 ms |
5140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
5132 KB |
Output is correct |
2 |
Correct |
15 ms |
5076 KB |
Output is correct |
3 |
Correct |
19 ms |
5164 KB |
Output is correct |
4 |
Correct |
16 ms |
5140 KB |
Output is correct |
5 |
Correct |
5 ms |
5460 KB |
Output is correct |
6 |
Correct |
5 ms |
5460 KB |
Output is correct |
7 |
Correct |
4 ms |
5460 KB |
Output is correct |
8 |
Correct |
5 ms |
5460 KB |
Output is correct |
9 |
Correct |
4 ms |
5460 KB |
Output is correct |
10 |
Correct |
4 ms |
5460 KB |
Output is correct |
11 |
Correct |
5 ms |
5496 KB |
Output is correct |
12 |
Correct |
5 ms |
5460 KB |
Output is correct |
13 |
Correct |
5 ms |
5508 KB |
Output is correct |
14 |
Correct |
4 ms |
5460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
306 ms |
48360 KB |
Output is correct |
2 |
Correct |
330 ms |
48128 KB |
Output is correct |
3 |
Correct |
411 ms |
48344 KB |
Output is correct |
4 |
Correct |
356 ms |
50016 KB |
Output is correct |
5 |
Correct |
361 ms |
49996 KB |
Output is correct |
6 |
Correct |
428 ms |
51684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
5132 KB |
Output is correct |
2 |
Correct |
15 ms |
5076 KB |
Output is correct |
3 |
Correct |
19 ms |
5164 KB |
Output is correct |
4 |
Correct |
16 ms |
5140 KB |
Output is correct |
5 |
Correct |
5 ms |
5460 KB |
Output is correct |
6 |
Correct |
5 ms |
5460 KB |
Output is correct |
7 |
Correct |
4 ms |
5460 KB |
Output is correct |
8 |
Correct |
5 ms |
5460 KB |
Output is correct |
9 |
Correct |
4 ms |
5460 KB |
Output is correct |
10 |
Correct |
4 ms |
5460 KB |
Output is correct |
11 |
Correct |
5 ms |
5496 KB |
Output is correct |
12 |
Correct |
5 ms |
5460 KB |
Output is correct |
13 |
Correct |
5 ms |
5508 KB |
Output is correct |
14 |
Correct |
4 ms |
5460 KB |
Output is correct |
15 |
Correct |
306 ms |
48360 KB |
Output is correct |
16 |
Correct |
330 ms |
48128 KB |
Output is correct |
17 |
Correct |
411 ms |
48344 KB |
Output is correct |
18 |
Correct |
356 ms |
50016 KB |
Output is correct |
19 |
Correct |
361 ms |
49996 KB |
Output is correct |
20 |
Correct |
428 ms |
51684 KB |
Output is correct |
21 |
Correct |
289 ms |
47604 KB |
Output is correct |
22 |
Correct |
309 ms |
47480 KB |
Output is correct |
23 |
Correct |
356 ms |
47692 KB |
Output is correct |
24 |
Correct |
342 ms |
49364 KB |
Output is correct |
25 |
Correct |
339 ms |
51836 KB |
Output is correct |
26 |
Correct |
311 ms |
47912 KB |
Output is correct |
27 |
Correct |
344 ms |
47800 KB |
Output is correct |
28 |
Correct |
315 ms |
47944 KB |
Output is correct |
29 |
Correct |
365 ms |
49184 KB |
Output is correct |
30 |
Correct |
387 ms |
50528 KB |
Output is correct |
31 |
Correct |
339 ms |
48396 KB |
Output is correct |
32 |
Correct |
347 ms |
48344 KB |
Output is correct |
33 |
Correct |
360 ms |
48512 KB |
Output is correct |
34 |
Correct |
390 ms |
50144 KB |
Output is correct |
35 |
Correct |
449 ms |
52504 KB |
Output is correct |
36 |
Correct |
377 ms |
50472 KB |
Output is correct |