#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const ll inf = 1e18;
vector<pair<int, int> > t[maxn];
int w[maxn];
int dw[maxn], h[maxn];
int Time, st[maxn], ft[maxn];
int par[maxn][18];
ll dis[maxn], dp[maxn], RMQ[maxn][18];
ll get(int v, int x){
ll ret = inf;
for (int i = 17; i >= 0; i--)
if (x & (1 << i)){
ret = min(ret, RMQ[v][i]);
v = par[v][i];
}
return ret;
}
void DFS(int v, int p = -1){
par[v][0] = p;
RMQ[v][0] = dp[v] - 2ll * dis[v];
for (int i = 1; i < 18 and par[v][i - 1] != -1; i++){
par[v][i] = par[par[v][i - 1]][i - 1];
RMQ[v][i] = min(RMQ[v][i - 1], RMQ[par[v][i - 1]][i - 1]);
}
for (auto u : t[v])
if (u.first != p)
DFS(u.first, v);
}
void dfs(int v, int p = -1){
st[v] = Time ++;
if (dp[v] == 0)
dp[v] = dis[v];
for (auto edge : t[v]){
int u = edge.first, e = edge.second;
if (u != p){
dw[e] = u;
dis[u] = dis[v] + w[e];
h[u] = h[v] + 1;
dfs(u, v);
dp[v] = min(dp[v], dp[u]);
}
}
ft[v] = Time;
}
int main(){
ios_base::sync_with_stdio(false);
int n, s, q, e;
cin >> n >> s >> q >> e;
for (int i = 1; i <= n - 1; i++){
int v, u;
cin >> v >> u >> w[i];
t[v].push_back({u, i});
t[u].push_back({v, i});
}
memset(dp, 63, sizeof dp);
for (int i = 1; i <= s; i++){
int c;
cin >> c;
dp[c] = 0;
}
memset(par, -1, sizeof par);
dfs(e);
DFS(e);
while (q --){
int e, v;
cin >> e >> v;
int u = dw[e];
if (st[u] <= st[v] and ft[v] <= ft[u]){
if (dp[u] > inf)
cout << "oo\n";
else
cout << dis[v] + get(v, h[v] - h[u] + 1) << '\n';
}
else
cout << "escaped\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
10744 KB |
Output is correct |
2 |
Correct |
40 ms |
10744 KB |
Output is correct |
3 |
Correct |
40 ms |
10744 KB |
Output is correct |
4 |
Correct |
40 ms |
10744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
10744 KB |
Output is correct |
2 |
Correct |
40 ms |
10744 KB |
Output is correct |
3 |
Correct |
40 ms |
10744 KB |
Output is correct |
4 |
Correct |
40 ms |
10744 KB |
Output is correct |
5 |
Correct |
14 ms |
10744 KB |
Output is correct |
6 |
Correct |
14 ms |
10872 KB |
Output is correct |
7 |
Correct |
14 ms |
10876 KB |
Output is correct |
8 |
Correct |
14 ms |
10872 KB |
Output is correct |
9 |
Correct |
15 ms |
10744 KB |
Output is correct |
10 |
Correct |
15 ms |
10872 KB |
Output is correct |
11 |
Correct |
15 ms |
10756 KB |
Output is correct |
12 |
Correct |
15 ms |
10792 KB |
Output is correct |
13 |
Correct |
14 ms |
10872 KB |
Output is correct |
14 |
Correct |
16 ms |
10876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
488 ms |
35952 KB |
Output is correct |
2 |
Correct |
466 ms |
35548 KB |
Output is correct |
3 |
Correct |
482 ms |
35364 KB |
Output is correct |
4 |
Correct |
504 ms |
36764 KB |
Output is correct |
5 |
Correct |
479 ms |
36884 KB |
Output is correct |
6 |
Correct |
518 ms |
38392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
10744 KB |
Output is correct |
2 |
Correct |
40 ms |
10744 KB |
Output is correct |
3 |
Correct |
40 ms |
10744 KB |
Output is correct |
4 |
Correct |
40 ms |
10744 KB |
Output is correct |
5 |
Correct |
14 ms |
10744 KB |
Output is correct |
6 |
Correct |
14 ms |
10872 KB |
Output is correct |
7 |
Correct |
14 ms |
10876 KB |
Output is correct |
8 |
Correct |
14 ms |
10872 KB |
Output is correct |
9 |
Correct |
15 ms |
10744 KB |
Output is correct |
10 |
Correct |
15 ms |
10872 KB |
Output is correct |
11 |
Correct |
15 ms |
10756 KB |
Output is correct |
12 |
Correct |
15 ms |
10792 KB |
Output is correct |
13 |
Correct |
14 ms |
10872 KB |
Output is correct |
14 |
Correct |
16 ms |
10876 KB |
Output is correct |
15 |
Correct |
488 ms |
35952 KB |
Output is correct |
16 |
Correct |
466 ms |
35548 KB |
Output is correct |
17 |
Correct |
482 ms |
35364 KB |
Output is correct |
18 |
Correct |
504 ms |
36764 KB |
Output is correct |
19 |
Correct |
479 ms |
36884 KB |
Output is correct |
20 |
Correct |
518 ms |
38392 KB |
Output is correct |
21 |
Correct |
422 ms |
35292 KB |
Output is correct |
22 |
Correct |
434 ms |
34992 KB |
Output is correct |
23 |
Correct |
455 ms |
34936 KB |
Output is correct |
24 |
Correct |
457 ms |
36572 KB |
Output is correct |
25 |
Correct |
516 ms |
38776 KB |
Output is correct |
26 |
Correct |
432 ms |
35280 KB |
Output is correct |
27 |
Correct |
434 ms |
35064 KB |
Output is correct |
28 |
Correct |
448 ms |
34980 KB |
Output is correct |
29 |
Correct |
522 ms |
36088 KB |
Output is correct |
30 |
Correct |
503 ms |
37240 KB |
Output is correct |
31 |
Correct |
429 ms |
35536 KB |
Output is correct |
32 |
Correct |
445 ms |
35192 KB |
Output is correct |
33 |
Correct |
460 ms |
35192 KB |
Output is correct |
34 |
Correct |
645 ms |
36712 KB |
Output is correct |
35 |
Correct |
504 ms |
38648 KB |
Output is correct |
36 |
Correct |
466 ms |
36604 KB |
Output is correct |