#include <bits/stdc++.h>
using namespace std;
#define int long long
#define oo 1e18
#define N 100005
#define log 20
#define fi first
#define se second
typedef pair<int, int> ii;
int n, q, s, e, dep[N], ds[N], par[log + 5][N], getdp[log + 5][N], dp[N], tin[N], tout[N], tim;
vector<ii> adj[N];
ii eg[N];
void init(int u, int p){
tin[u] = ++tim;
for (auto x : adj[u]){
if (x.fi == p) continue;
dep[x.fi] = dep[u] + 1;
ds[x.fi] = ds[u] + x.se;
par[0][x.fi] = u;
init(x.fi, u);
dp[u] = min(dp[u], dp[x.fi] + x.se);
}
tout[u] = tim;
}
void init2(int u, int p){
for (auto x : adj[u]){
if (x.fi == p) continue;
getdp[0][x.fi] = dp[u] - ds[u];
init2(x.fi, u);
}
}
bool in(int u, int v){
return (tin[v] >= tin[u] && tout[v] <= tout[u]);
}
int get(int u, int len){
int rt = oo;
for (int k = log; k >= 0; k--){
if ((1ll << k) <= len){
len -= (1ll << k);
rt = min(rt, getdp[k][u]);
u = par[k][u];
}
}
return rt;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> s >> q >> e;
dp[n] = oo;
for (int i = 1; i <= n - 1; i++){
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
dp[i] = oo;
eg[i] = {u, v};
}
for (int i = 1; i <= s; i++){
int u;
cin >> u;
dp[u] = 0;
}
dep[e] = 1;
init(e, 0);
init2(e, 0);
for (int k = 1; k <= log; k++){
for (int i = 1; i <= n; i++){
par[k][i] = par[k - 1][par[k - 1][i]];
getdp[k][i] = min(getdp[k - 1][i], getdp[k - 1][par[k - 1][i]]);
}
}
while (q--){
int idx, x;
cin >> idx >> x;
int u = eg[idx].fi, v = eg[idx].se;
if (par[0][v] != u) swap(u, v);
if (!in(v, x)){
cout << "escaped\n";
continue;
}
if (dp[v] == oo){
cout << "oo\n";
continue;
}
cout << min(dp[x], ds[x] + get(x, dep[x] - dep[v])) << "\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
41560 KB |
Output is correct |
2 |
Correct |
7 ms |
41560 KB |
Output is correct |
3 |
Correct |
8 ms |
41560 KB |
Output is correct |
4 |
Correct |
8 ms |
41760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
41560 KB |
Output is correct |
2 |
Correct |
7 ms |
41560 KB |
Output is correct |
3 |
Correct |
8 ms |
41560 KB |
Output is correct |
4 |
Correct |
8 ms |
41760 KB |
Output is correct |
5 |
Correct |
7 ms |
41560 KB |
Output is correct |
6 |
Correct |
7 ms |
41560 KB |
Output is correct |
7 |
Correct |
7 ms |
41560 KB |
Output is correct |
8 |
Correct |
7 ms |
41560 KB |
Output is correct |
9 |
Correct |
7 ms |
41560 KB |
Output is correct |
10 |
Correct |
7 ms |
41560 KB |
Output is correct |
11 |
Correct |
7 ms |
41560 KB |
Output is correct |
12 |
Correct |
6 ms |
41560 KB |
Output is correct |
13 |
Correct |
8 ms |
41560 KB |
Output is correct |
14 |
Correct |
7 ms |
41560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
85 ms |
52976 KB |
Output is correct |
2 |
Correct |
95 ms |
52500 KB |
Output is correct |
3 |
Correct |
96 ms |
52816 KB |
Output is correct |
4 |
Correct |
116 ms |
54712 KB |
Output is correct |
5 |
Correct |
99 ms |
54892 KB |
Output is correct |
6 |
Correct |
128 ms |
56804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
41560 KB |
Output is correct |
2 |
Correct |
7 ms |
41560 KB |
Output is correct |
3 |
Correct |
8 ms |
41560 KB |
Output is correct |
4 |
Correct |
8 ms |
41760 KB |
Output is correct |
5 |
Correct |
7 ms |
41560 KB |
Output is correct |
6 |
Correct |
7 ms |
41560 KB |
Output is correct |
7 |
Correct |
7 ms |
41560 KB |
Output is correct |
8 |
Correct |
7 ms |
41560 KB |
Output is correct |
9 |
Correct |
7 ms |
41560 KB |
Output is correct |
10 |
Correct |
7 ms |
41560 KB |
Output is correct |
11 |
Correct |
7 ms |
41560 KB |
Output is correct |
12 |
Correct |
6 ms |
41560 KB |
Output is correct |
13 |
Correct |
8 ms |
41560 KB |
Output is correct |
14 |
Correct |
7 ms |
41560 KB |
Output is correct |
15 |
Correct |
85 ms |
52976 KB |
Output is correct |
16 |
Correct |
95 ms |
52500 KB |
Output is correct |
17 |
Correct |
96 ms |
52816 KB |
Output is correct |
18 |
Correct |
116 ms |
54712 KB |
Output is correct |
19 |
Correct |
99 ms |
54892 KB |
Output is correct |
20 |
Correct |
128 ms |
56804 KB |
Output is correct |
21 |
Correct |
74 ms |
52120 KB |
Output is correct |
22 |
Correct |
92 ms |
52372 KB |
Output is correct |
23 |
Correct |
81 ms |
52304 KB |
Output is correct |
24 |
Correct |
95 ms |
54264 KB |
Output is correct |
25 |
Correct |
114 ms |
57288 KB |
Output is correct |
26 |
Correct |
73 ms |
52360 KB |
Output is correct |
27 |
Correct |
90 ms |
52568 KB |
Output is correct |
28 |
Correct |
83 ms |
52332 KB |
Output is correct |
29 |
Correct |
107 ms |
53840 KB |
Output is correct |
30 |
Correct |
126 ms |
55376 KB |
Output is correct |
31 |
Correct |
79 ms |
52304 KB |
Output is correct |
32 |
Correct |
92 ms |
52172 KB |
Output is correct |
33 |
Correct |
96 ms |
52476 KB |
Output is correct |
34 |
Correct |
127 ms |
54820 KB |
Output is correct |
35 |
Correct |
120 ms |
57168 KB |
Output is correct |
36 |
Correct |
102 ms |
54360 KB |
Output is correct |