#include <iostream>
#include <vector>
#define int long long
using namespace std;
const int mx=1000000000000000000;
struct edge{
int u,v,w;
}ed[100001];
int n,s,q,e,st[100001],en[100001],dp[100001],id,c[100001],u,d[100001],p[100001][20],mn[100001][20];
vector <pair <int, int> > ke[100001];
void dfs(int u, int p){
st[u]=++id;
if (!c[u])
dp[u]=mx;
for (auto v:ke[u])
if (v.first!=p){
d[v.first]=d[u]+v.second;
dfs(v.first,u);
dp[u]=min(dp[u],dp[v.first]+v.second);
}
en[u]=++id;
}
void dfs2(int u, int par){
for (auto v:ke[u])
if (v.first!=par){
p[v.first][0]=u;
mn[v.first][0]=dp[u];
dfs2(v.first,u);
}
}
bool isancestor(int i, int j){
return (st[i]<=st[j]&&en[i]>=en[j]);
}
void prep(){
for (int i=1;i<20;i++)
for (int j=1;j<=n;j++){
p[j][i]=p[p[j][i-1]][i-1];
mn[j][i]=min(mn[j][i-1],mn[p[j][i-1]][i-1]);
}
}
int f(int i, int j){
int res=dp[i];
for (int k=19;k>=0;k--)
if (p[i][k]&&d[p[i][k]]>d[j]){
res=min(res,mn[i][k]);
i=p[i][k];
}
res=min(res,dp[j]);
return res;
}
signed main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
cin >> n >> s >> q >> e;
for (int i=1;i<n;i++){
cin >> ed[i].u >> ed[i].v >> ed[i].w;
ke[ed[i].u].push_back({ed[i].v,ed[i].w});
ke[ed[i].v].push_back({ed[i].u,ed[i].w});
}
for (int i=0;i<s;i++){
cin >> u;
c[u]=1;
}
dfs(e,e);
for (int i=1;i<=n;i++)
if (dp[i]!=mx)
dp[i]-=d[i];
dfs2(e,e);
prep();
int i,r;
while (q--){
cin >> i >> r;
if (d[ed[i].u]<d[ed[i].v])
swap(ed[i].u,ed[i].v);
int u=ed[i].u;
if (!isancestor(u,r)){
cout << "escaped\n";
continue;
}
int res=f(r,u);
if (res==mx)
cout << "oo\n";
else
cout << res+d[r] << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2772 KB |
Output is correct |
2 |
Correct |
5 ms |
2820 KB |
Output is correct |
3 |
Correct |
4 ms |
2828 KB |
Output is correct |
4 |
Correct |
3 ms |
2820 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2772 KB |
Output is correct |
2 |
Correct |
5 ms |
2820 KB |
Output is correct |
3 |
Correct |
4 ms |
2828 KB |
Output is correct |
4 |
Correct |
3 ms |
2820 KB |
Output is correct |
5 |
Correct |
3 ms |
3288 KB |
Output is correct |
6 |
Correct |
3 ms |
3156 KB |
Output is correct |
7 |
Correct |
3 ms |
3156 KB |
Output is correct |
8 |
Correct |
2 ms |
3136 KB |
Output is correct |
9 |
Correct |
3 ms |
3156 KB |
Output is correct |
10 |
Correct |
4 ms |
3072 KB |
Output is correct |
11 |
Correct |
3 ms |
3156 KB |
Output is correct |
12 |
Correct |
3 ms |
3156 KB |
Output is correct |
13 |
Correct |
3 ms |
3156 KB |
Output is correct |
14 |
Correct |
3 ms |
3200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
156 ms |
46028 KB |
Output is correct |
2 |
Correct |
182 ms |
45748 KB |
Output is correct |
3 |
Correct |
226 ms |
46048 KB |
Output is correct |
4 |
Correct |
200 ms |
47892 KB |
Output is correct |
5 |
Correct |
183 ms |
48060 KB |
Output is correct |
6 |
Correct |
226 ms |
50152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2772 KB |
Output is correct |
2 |
Correct |
5 ms |
2820 KB |
Output is correct |
3 |
Correct |
4 ms |
2828 KB |
Output is correct |
4 |
Correct |
3 ms |
2820 KB |
Output is correct |
5 |
Correct |
3 ms |
3288 KB |
Output is correct |
6 |
Correct |
3 ms |
3156 KB |
Output is correct |
7 |
Correct |
3 ms |
3156 KB |
Output is correct |
8 |
Correct |
2 ms |
3136 KB |
Output is correct |
9 |
Correct |
3 ms |
3156 KB |
Output is correct |
10 |
Correct |
4 ms |
3072 KB |
Output is correct |
11 |
Correct |
3 ms |
3156 KB |
Output is correct |
12 |
Correct |
3 ms |
3156 KB |
Output is correct |
13 |
Correct |
3 ms |
3156 KB |
Output is correct |
14 |
Correct |
3 ms |
3200 KB |
Output is correct |
15 |
Correct |
156 ms |
46028 KB |
Output is correct |
16 |
Correct |
182 ms |
45748 KB |
Output is correct |
17 |
Correct |
226 ms |
46048 KB |
Output is correct |
18 |
Correct |
200 ms |
47892 KB |
Output is correct |
19 |
Correct |
183 ms |
48060 KB |
Output is correct |
20 |
Correct |
226 ms |
50152 KB |
Output is correct |
21 |
Correct |
166 ms |
48460 KB |
Output is correct |
22 |
Correct |
201 ms |
48304 KB |
Output is correct |
23 |
Correct |
178 ms |
48548 KB |
Output is correct |
24 |
Correct |
201 ms |
50680 KB |
Output is correct |
25 |
Correct |
218 ms |
53684 KB |
Output is correct |
26 |
Correct |
153 ms |
48868 KB |
Output is correct |
27 |
Correct |
169 ms |
48716 KB |
Output is correct |
28 |
Correct |
223 ms |
48936 KB |
Output is correct |
29 |
Correct |
200 ms |
50412 KB |
Output is correct |
30 |
Correct |
231 ms |
52016 KB |
Output is correct |
31 |
Correct |
153 ms |
49360 KB |
Output is correct |
32 |
Correct |
177 ms |
49308 KB |
Output is correct |
33 |
Correct |
184 ms |
49664 KB |
Output is correct |
34 |
Correct |
212 ms |
51444 KB |
Output is correct |
35 |
Correct |
216 ms |
54348 KB |
Output is correct |
36 |
Correct |
209 ms |
51476 KB |
Output is correct |