#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int ll
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
const ll maxn = 1e5 + 5;
const ll inf = LLONG_MAX/2;
int N, S, Q, E;
ii road[maxn];
vii adj[maxn];
set<int> shop;
vi tin(maxn);
vi tout(maxn);
vll dist(maxn, inf);
int par[maxn][20];
ll par_w[maxn][20];
ll par_s[maxn][20];
int cnt = 0;
void dfs(int u) {
tin[u] = cnt; cnt++;
for(auto [v, w] : adj[u]) if(v != par[u][0]) {
par[v][0] = u;
par_w[v][0] = w;
dfs(v);
dist[u] = min(dist[u], dist[v] + w);
}
if(shop.count(u)) dist[u] = 0;
tout[u] = cnt; cnt++;
}
bool is_anc(int v, int anc) {
return tin[v] >= tin[anc] && tout[v] <= tout[anc];
}
void lifting() {
for(int j = 1; j <= N; j++) {
par_s[j][0] = min(par_w[j][0] + dist[par[j][0]], dist[j]);
}
for(int i = 1; i <= 19; i++) for(int j = 1; j <= N; j++) {
par[j][i] = par[par[j][i-1]][i-1];
par_w[j][i] = par_w[par[j][i-1]][i-1] + par_w[j][i-1];
par_s[j][i] = min(par_s[j][i-1], par_s[par[j][i-1]][i-1] + par_w[j][i-1]);
}
}
int32_t main() {
cin >> N >> S >> Q >> E;
int u, v, w;
for(int i = 1; i < N; i++) {
cin >> u >> v >> w;
road[i] = {u, v};
adj[u].pb({v, w});
adj[v].pb({u, w});
}
for(int i = 0; i < S; i++) {
cin >> v; shop.insert(v);
}
par[E][0] = E;
par_w[E][0] = 0;
dfs(E);
lifting();
int I, R, top;
ll res;
while(Q--) {
cin >> R >> I;
auto [u, v] = road[R];
if(is_anc(I, u) && is_anc(I, v)) {
top = (is_anc(u, v) ? u : v);
int x = I;
ll wt = 0;
res = dist[I];
for(int i = 19; i >= 0; i--) if(is_anc(par[x][i], top)) {
res = min(res, par_s[x][i] + wt);
wt += par_w[x][i];
x = par[x][i];
}
if(res < inf) cout << res << endl;
else cout << "oo" << endl;
} else {
cout << "escaped" << endl;
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
5196 KB |
Output is correct |
2 |
Correct |
25 ms |
5196 KB |
Output is correct |
3 |
Correct |
24 ms |
5228 KB |
Output is correct |
4 |
Correct |
23 ms |
5216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
5196 KB |
Output is correct |
2 |
Correct |
25 ms |
5196 KB |
Output is correct |
3 |
Correct |
24 ms |
5228 KB |
Output is correct |
4 |
Correct |
23 ms |
5216 KB |
Output is correct |
5 |
Correct |
6 ms |
5608 KB |
Output is correct |
6 |
Correct |
6 ms |
5580 KB |
Output is correct |
7 |
Correct |
6 ms |
5580 KB |
Output is correct |
8 |
Correct |
7 ms |
5620 KB |
Output is correct |
9 |
Correct |
7 ms |
5504 KB |
Output is correct |
10 |
Correct |
7 ms |
5636 KB |
Output is correct |
11 |
Correct |
8 ms |
5580 KB |
Output is correct |
12 |
Correct |
7 ms |
5552 KB |
Output is correct |
13 |
Correct |
7 ms |
5580 KB |
Output is correct |
14 |
Correct |
7 ms |
5580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
589 ms |
67680 KB |
Output is correct |
2 |
Correct |
644 ms |
67804 KB |
Output is correct |
3 |
Correct |
663 ms |
67836 KB |
Output is correct |
4 |
Correct |
668 ms |
69800 KB |
Output is correct |
5 |
Correct |
653 ms |
69872 KB |
Output is correct |
6 |
Correct |
714 ms |
72068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
5196 KB |
Output is correct |
2 |
Correct |
25 ms |
5196 KB |
Output is correct |
3 |
Correct |
24 ms |
5228 KB |
Output is correct |
4 |
Correct |
23 ms |
5216 KB |
Output is correct |
5 |
Correct |
6 ms |
5608 KB |
Output is correct |
6 |
Correct |
6 ms |
5580 KB |
Output is correct |
7 |
Correct |
6 ms |
5580 KB |
Output is correct |
8 |
Correct |
7 ms |
5620 KB |
Output is correct |
9 |
Correct |
7 ms |
5504 KB |
Output is correct |
10 |
Correct |
7 ms |
5636 KB |
Output is correct |
11 |
Correct |
8 ms |
5580 KB |
Output is correct |
12 |
Correct |
7 ms |
5552 KB |
Output is correct |
13 |
Correct |
7 ms |
5580 KB |
Output is correct |
14 |
Correct |
7 ms |
5580 KB |
Output is correct |
15 |
Correct |
589 ms |
67680 KB |
Output is correct |
16 |
Correct |
644 ms |
67804 KB |
Output is correct |
17 |
Correct |
663 ms |
67836 KB |
Output is correct |
18 |
Correct |
668 ms |
69800 KB |
Output is correct |
19 |
Correct |
653 ms |
69872 KB |
Output is correct |
20 |
Correct |
714 ms |
72068 KB |
Output is correct |
21 |
Correct |
514 ms |
62820 KB |
Output is correct |
22 |
Correct |
570 ms |
62428 KB |
Output is correct |
23 |
Correct |
523 ms |
62756 KB |
Output is correct |
24 |
Correct |
630 ms |
64700 KB |
Output is correct |
25 |
Correct |
625 ms |
67752 KB |
Output is correct |
26 |
Correct |
500 ms |
62560 KB |
Output is correct |
27 |
Correct |
515 ms |
62412 KB |
Output is correct |
28 |
Correct |
517 ms |
62724 KB |
Output is correct |
29 |
Correct |
573 ms |
64188 KB |
Output is correct |
30 |
Correct |
596 ms |
65740 KB |
Output is correct |
31 |
Correct |
528 ms |
63244 KB |
Output is correct |
32 |
Correct |
572 ms |
63064 KB |
Output is correct |
33 |
Correct |
535 ms |
63240 KB |
Output is correct |
34 |
Correct |
616 ms |
65164 KB |
Output is correct |
35 |
Correct |
598 ms |
68120 KB |
Output is correct |
36 |
Correct |
600 ms |
65796 KB |
Output is correct |