#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
int in[N], out[N], timer, P[20][N], dep[N];
vector<tuple<int, int, int>> edge;
vector<pair<int, int>> g[N];
ll dp[N], dp2[N], O[20][N];
void dfs(int now, int par)
{
P[0][now] = par; dep[now] = dep[par]+1;
in[now] = timer++;
for (auto [w, v] : g[now]) if (v != par) dp2[v] = dp2[now] + w, dfs(v, now), dp[now] = min(dp[now], w + dp[v]);
out[now] = timer++;
O[0][now] = dp[now] - dp2[now];
// printf("O %d: %lld dp: %lld dp2: %lld\n", now, O[0][now], dp[now], dp2[now]);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,s,q,e; cin >> n >> s >> q >> e;
memset(dp, 63, sizeof dp), memset(O, 63, sizeof O);
edge.resize(n-1);
for (auto &[u, v, w] : edge) cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u);
int c;
while(s--) cin >> c, dp[c] = 0;
dfs(e,e);
for (int j = 1; j < 20; ++j)
for (int u = 1; u <= n; ++u) P[j][u] = P[j-1][P[j-1][u]], O[j][u] = min(O[j-1][P[j-1][u]], O[j-1][u]);
// for (int j = 0; j < 20; ++j){
// for (int u = 1; u <= n; ++u) cout << O[j][u] << " ";
// cout << '\n';
// }
// for(int i=1;i<=n;i++) cout << in[i] << " " << out[i] << '\n';
for (int i, u; q--;)
{
cin >> i >> u;
int v = get<0>(edge[i-1]) == u ? get<1>(edge[i-1]) : get<0>(edge[i-1]), v2 = get<0>(edge[i-1]) == v ? get<1>(edge[i-1]) : get<0>(edge[i-1]);
if (P[0][v2] == v) swap(v, v2);
if (in[v] <= in[u] && out[u] <= out[v])
{
ll z = min(dp[u], dp[v] - dp2[v] + dp2[u]), u0 = u, dt = dep[u]-dep[v];
for (int j = 20; j--;) if (dt & (1 << j)) z = min(z, dp2[u0] + O[j][u]), u = P[j][u];
(z < 1e15 ? (cout << z << '\n') : cout << "oo\n");
}
else cout << "escaped\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
54108 KB |
Output is correct |
2 |
Correct |
8 ms |
54108 KB |
Output is correct |
3 |
Correct |
8 ms |
53976 KB |
Output is correct |
4 |
Correct |
9 ms |
54108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
54108 KB |
Output is correct |
2 |
Correct |
8 ms |
54108 KB |
Output is correct |
3 |
Correct |
8 ms |
53976 KB |
Output is correct |
4 |
Correct |
9 ms |
54108 KB |
Output is correct |
5 |
Correct |
8 ms |
54108 KB |
Output is correct |
6 |
Correct |
7 ms |
54108 KB |
Output is correct |
7 |
Correct |
7 ms |
54108 KB |
Output is correct |
8 |
Correct |
7 ms |
54108 KB |
Output is correct |
9 |
Correct |
7 ms |
54108 KB |
Output is correct |
10 |
Correct |
7 ms |
53952 KB |
Output is correct |
11 |
Correct |
7 ms |
54108 KB |
Output is correct |
12 |
Correct |
7 ms |
54108 KB |
Output is correct |
13 |
Correct |
7 ms |
54124 KB |
Output is correct |
14 |
Correct |
7 ms |
54108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
86 ms |
65172 KB |
Output is correct |
2 |
Correct |
82 ms |
64852 KB |
Output is correct |
3 |
Correct |
78 ms |
64856 KB |
Output is correct |
4 |
Correct |
86 ms |
66388 KB |
Output is correct |
5 |
Correct |
78 ms |
66736 KB |
Output is correct |
6 |
Correct |
88 ms |
68436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
54108 KB |
Output is correct |
2 |
Correct |
8 ms |
54108 KB |
Output is correct |
3 |
Correct |
8 ms |
53976 KB |
Output is correct |
4 |
Correct |
9 ms |
54108 KB |
Output is correct |
5 |
Correct |
8 ms |
54108 KB |
Output is correct |
6 |
Correct |
7 ms |
54108 KB |
Output is correct |
7 |
Correct |
7 ms |
54108 KB |
Output is correct |
8 |
Correct |
7 ms |
54108 KB |
Output is correct |
9 |
Correct |
7 ms |
54108 KB |
Output is correct |
10 |
Correct |
7 ms |
53952 KB |
Output is correct |
11 |
Correct |
7 ms |
54108 KB |
Output is correct |
12 |
Correct |
7 ms |
54108 KB |
Output is correct |
13 |
Correct |
7 ms |
54124 KB |
Output is correct |
14 |
Correct |
7 ms |
54108 KB |
Output is correct |
15 |
Correct |
86 ms |
65172 KB |
Output is correct |
16 |
Correct |
82 ms |
64852 KB |
Output is correct |
17 |
Correct |
78 ms |
64856 KB |
Output is correct |
18 |
Correct |
86 ms |
66388 KB |
Output is correct |
19 |
Correct |
78 ms |
66736 KB |
Output is correct |
20 |
Correct |
88 ms |
68436 KB |
Output is correct |
21 |
Correct |
64 ms |
64600 KB |
Output is correct |
22 |
Correct |
69 ms |
64340 KB |
Output is correct |
23 |
Correct |
70 ms |
64336 KB |
Output is correct |
24 |
Correct |
74 ms |
66264 KB |
Output is correct |
25 |
Correct |
79 ms |
69092 KB |
Output is correct |
26 |
Correct |
67 ms |
64592 KB |
Output is correct |
27 |
Correct |
66 ms |
64244 KB |
Output is correct |
28 |
Correct |
69 ms |
64336 KB |
Output is correct |
29 |
Correct |
89 ms |
65936 KB |
Output is correct |
30 |
Correct |
77 ms |
67152 KB |
Output is correct |
31 |
Correct |
64 ms |
64592 KB |
Output is correct |
32 |
Correct |
71 ms |
64344 KB |
Output is correct |
33 |
Correct |
75 ms |
64368 KB |
Output is correct |
34 |
Correct |
98 ms |
66132 KB |
Output is correct |
35 |
Correct |
78 ms |
68904 KB |
Output is correct |
36 |
Correct |
84 ms |
66388 KB |
Output is correct |