#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int MAX = 2e17;
const int N = 1e5;
const int LOG = 17;
int n, s, q, e;
vector< pair<int, int> > g[N + 1];
vector< pair<int, int> > edges;
int is_shop[N+1], depth_sum[N+1];
int depth[N+1], tin[N+1], tout[N+1];
int timer, la[N*2][LOG + 5] ,up[N+1][LOG+2];
int lg[N*2 + 100], dist_shop[N + 10];
void dfs(int v, int par){
tin[v] = timer++;
up[v][0] = par;
for(int j = 1;j <= LOG; j++){
up[v][j] = up[up[v][j-1]][j-1];
}
int distance = MAX;
for(auto [to, w] : g[v]){
if(to == par) continue;
depth[to] = depth[v] + 1;
depth_sum[to] = depth_sum[v] + w;
dfs(to, v);
distance = min(distance, dist_shop[to] + w);
}
if(is_shop[v]){
dist_shop[v] = 0;
}else{
dist_shop[v] = distance;
}
tout[v] = timer;
}
int is_parent(int par, int v){
return (tin[par] <= tin[v] && tout[v] <= tout[par]);
}
int close(int idx){
return (depth[edges[idx].ff] < depth[edges[idx].ss] ? edges[idx].ss : edges[idx].ff);
}
main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> s >> q >> e;
edges.push_back({-1, -1});
for(int i = 1;i < n; i++){
int a, b, w; cin >> a >> b >> w;
g[a].push_back({b, w});
g[b].push_back({a, w});
edges.push_back({a, b});
}
// for(auto [x, y] : edges){
// cout << x << ' ' << y << '\n';
// }
// cout << "\n" << '\n';
for(int i = 0;i < s; i++){
int x; cin >> x;
is_shop[x] = 1;
}
dfs(e, e);
for(int j = 0;j <= LOG; j++){
for(int i = 1;i <= N; i++){
if(j == 0){
la[i][j] = dist_shop[i] - depth_sum[i];
}else{
la[i][j] = min(la[i][j-1], la[up[i][j-1]][j-1]);
}
}
}
while(q--){
int idx, v; cin >> idx >> v;
// cout << edges[idx].ff << ' ' << edges[idx].ss << '\n';
// cout << v << " = " << close(idx) << '\n';
if(!is_parent(close(idx), v)){
cout << "escaped";
}else{
int k = depth[v] - depth[close(idx)];
int mn = dist_shop[v], vert = v;
for(int i = 0;i < LOG; i++){
if(k & (1<<i)){
mn = min(mn, la[vert][i] + depth_sum[v]);
vert = up[vert][i];
}
}
mn = min(mn, la[vert][0] + depth_sum[v]);
// cout << k << " = " << mn << '\n';
if(mn >= (int)1e15) cout << "oo";
else cout << mn;
}
cout << '\n';
}
return 0;
}
Compilation message
valley.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
45 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
25432 KB |
Output is correct |
2 |
Correct |
18 ms |
25436 KB |
Output is correct |
3 |
Correct |
16 ms |
25436 KB |
Output is correct |
4 |
Correct |
16 ms |
25436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
25432 KB |
Output is correct |
2 |
Correct |
18 ms |
25436 KB |
Output is correct |
3 |
Correct |
16 ms |
25436 KB |
Output is correct |
4 |
Correct |
16 ms |
25436 KB |
Output is correct |
5 |
Correct |
16 ms |
25436 KB |
Output is correct |
6 |
Correct |
16 ms |
25436 KB |
Output is correct |
7 |
Correct |
14 ms |
25564 KB |
Output is correct |
8 |
Correct |
14 ms |
25436 KB |
Output is correct |
9 |
Correct |
15 ms |
25436 KB |
Output is correct |
10 |
Correct |
14 ms |
25432 KB |
Output is correct |
11 |
Correct |
15 ms |
25436 KB |
Output is correct |
12 |
Correct |
15 ms |
25432 KB |
Output is correct |
13 |
Correct |
14 ms |
25432 KB |
Output is correct |
14 |
Correct |
15 ms |
25572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
123 ms |
52304 KB |
Output is correct |
2 |
Correct |
117 ms |
52672 KB |
Output is correct |
3 |
Correct |
123 ms |
52924 KB |
Output is correct |
4 |
Correct |
132 ms |
54772 KB |
Output is correct |
5 |
Correct |
121 ms |
54976 KB |
Output is correct |
6 |
Correct |
143 ms |
57112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
25432 KB |
Output is correct |
2 |
Correct |
18 ms |
25436 KB |
Output is correct |
3 |
Correct |
16 ms |
25436 KB |
Output is correct |
4 |
Correct |
16 ms |
25436 KB |
Output is correct |
5 |
Correct |
16 ms |
25436 KB |
Output is correct |
6 |
Correct |
16 ms |
25436 KB |
Output is correct |
7 |
Correct |
14 ms |
25564 KB |
Output is correct |
8 |
Correct |
14 ms |
25436 KB |
Output is correct |
9 |
Correct |
15 ms |
25436 KB |
Output is correct |
10 |
Correct |
14 ms |
25432 KB |
Output is correct |
11 |
Correct |
15 ms |
25436 KB |
Output is correct |
12 |
Correct |
15 ms |
25432 KB |
Output is correct |
13 |
Correct |
14 ms |
25432 KB |
Output is correct |
14 |
Correct |
15 ms |
25572 KB |
Output is correct |
15 |
Correct |
123 ms |
52304 KB |
Output is correct |
16 |
Correct |
117 ms |
52672 KB |
Output is correct |
17 |
Correct |
123 ms |
52924 KB |
Output is correct |
18 |
Correct |
132 ms |
54772 KB |
Output is correct |
19 |
Correct |
121 ms |
54976 KB |
Output is correct |
20 |
Correct |
143 ms |
57112 KB |
Output is correct |
21 |
Correct |
128 ms |
52412 KB |
Output is correct |
22 |
Correct |
116 ms |
52296 KB |
Output is correct |
23 |
Correct |
138 ms |
52416 KB |
Output is correct |
24 |
Correct |
133 ms |
54516 KB |
Output is correct |
25 |
Correct |
136 ms |
57532 KB |
Output is correct |
26 |
Correct |
105 ms |
52412 KB |
Output is correct |
27 |
Correct |
110 ms |
52412 KB |
Output is correct |
28 |
Correct |
117 ms |
52480 KB |
Output is correct |
29 |
Correct |
141 ms |
53984 KB |
Output is correct |
30 |
Correct |
130 ms |
55420 KB |
Output is correct |
31 |
Correct |
104 ms |
52352 KB |
Output is correct |
32 |
Correct |
131 ms |
52404 KB |
Output is correct |
33 |
Correct |
116 ms |
52672 KB |
Output is correct |
34 |
Correct |
143 ms |
54392 KB |
Output is correct |
35 |
Correct |
127 ms |
57256 KB |
Output is correct |
36 |
Correct |
124 ms |
54424 KB |
Output is correct |