#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#define DUZO 1000000000000000LL;
using namespace std;
long long n,s,q,e,a,b,c,parnt[20][100005],dpth[100005],ord[2][100005],l;
long long il[20][100005],dl[20][100005],x,y;
bool czy[100005];
vector<pair<long long,long long>> v[100005];
long long krw[2][100005];
long long DFS(long long x,long long f){
l++;
ord[0][x]=l;
parnt[0][x]=f;
long long wyn=DUZO;
if(czy[x]) wyn=0;
//cerr<<x<<" "<<dpth[x]<<"p\n";
for(auto u:v[x]){
if(u.first==f) continue;
dpth[u.first]=dpth[x]+1;
//cerr<<u.first<<" "<<x<<"!!!\n";
dl[0][u.first]=u.second;
wyn=min(wyn,u.second+DFS(u.first,x));
}
//cerr<<x<<" "<<dpth[x]<<"\n";
il[0][x]=wyn;
ord[1][x]=l;
return wyn;
}
int main(){
ios_base::sync_with_stdio(0);
cin>>n>>s>>q>>e;
for(long long i=1;i<n;i++){
//prnt[0][i]=i;
cin>>a>>b>>c;
v[a].push_back({b,c});
v[b].push_back({a,c});
krw[0][i]=a;
krw[1][i]=b;
}
for(long long i=0;i<s;i++){
cin>>a;
czy[a]=1;
}
DFS(e,-1);
parnt[0][e]=e;
for(long long i=1;i<20;i++)
for(long long u=1;u<=n;u++){
parnt[i][u]=parnt[i-1][parnt[i-1][u]];
dl[i][u]=dl[i-1][u]+dl[i-1][parnt[i-1][u]];
il[i][u]=min(il[i-1][u],il[i-1][parnt[i-1][u]]+dl[i-1][u]);
}
for(long long i=0;i<q;i++){
cin>>a>>c;
b=krw[1][a];
a=krw[0][a];
//cerr<<dpth[a]<<" "<<dpth[b]<<"!!\n";
if(dpth[a]<dpth[b]) swap(a,b); //a nizej b wyzej
//cerr<<a<<" "<<ord[0][a]<<" "<<ord[1][a]<<" "<<c<<" "<<ord[0][c]<<"\n";
if(ord[0][a]<=ord[0][c] && ord[0][c]<=ord[1][a]){
x=DUZO;
y=0;
a=c;
//cerr<<b<<"!!!\n";
for(long long u=19;u>=0;u--){
if(dpth[parnt[u][a]]>dpth[b]){
x=min(il[u][a]+y,x);
y+=dl[u][a];
a=parnt[u][a];
}
}
x=min(x,y+il[0][a]);
if(x==1000000000000000LL)
cout<<"oo\n";
else
cout<<x<<"\n";
}else
cout<<"escaped\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
3028 KB |
Output is correct |
2 |
Correct |
16 ms |
3204 KB |
Output is correct |
3 |
Correct |
17 ms |
3212 KB |
Output is correct |
4 |
Correct |
15 ms |
3156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
3028 KB |
Output is correct |
2 |
Correct |
16 ms |
3204 KB |
Output is correct |
3 |
Correct |
17 ms |
3212 KB |
Output is correct |
4 |
Correct |
15 ms |
3156 KB |
Output is correct |
5 |
Correct |
4 ms |
3540 KB |
Output is correct |
6 |
Correct |
4 ms |
3572 KB |
Output is correct |
7 |
Correct |
5 ms |
3540 KB |
Output is correct |
8 |
Correct |
4 ms |
3540 KB |
Output is correct |
9 |
Correct |
4 ms |
3540 KB |
Output is correct |
10 |
Correct |
4 ms |
3540 KB |
Output is correct |
11 |
Correct |
4 ms |
3572 KB |
Output is correct |
12 |
Correct |
4 ms |
3540 KB |
Output is correct |
13 |
Correct |
5 ms |
3540 KB |
Output is correct |
14 |
Correct |
5 ms |
3524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
284 ms |
59392 KB |
Output is correct |
2 |
Correct |
270 ms |
59176 KB |
Output is correct |
3 |
Correct |
308 ms |
59412 KB |
Output is correct |
4 |
Correct |
298 ms |
61292 KB |
Output is correct |
5 |
Correct |
313 ms |
61624 KB |
Output is correct |
6 |
Correct |
340 ms |
63684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
3028 KB |
Output is correct |
2 |
Correct |
16 ms |
3204 KB |
Output is correct |
3 |
Correct |
17 ms |
3212 KB |
Output is correct |
4 |
Correct |
15 ms |
3156 KB |
Output is correct |
5 |
Correct |
4 ms |
3540 KB |
Output is correct |
6 |
Correct |
4 ms |
3572 KB |
Output is correct |
7 |
Correct |
5 ms |
3540 KB |
Output is correct |
8 |
Correct |
4 ms |
3540 KB |
Output is correct |
9 |
Correct |
4 ms |
3540 KB |
Output is correct |
10 |
Correct |
4 ms |
3540 KB |
Output is correct |
11 |
Correct |
4 ms |
3572 KB |
Output is correct |
12 |
Correct |
4 ms |
3540 KB |
Output is correct |
13 |
Correct |
5 ms |
3540 KB |
Output is correct |
14 |
Correct |
5 ms |
3524 KB |
Output is correct |
15 |
Correct |
284 ms |
59392 KB |
Output is correct |
16 |
Correct |
270 ms |
59176 KB |
Output is correct |
17 |
Correct |
308 ms |
59412 KB |
Output is correct |
18 |
Correct |
298 ms |
61292 KB |
Output is correct |
19 |
Correct |
313 ms |
61624 KB |
Output is correct |
20 |
Correct |
340 ms |
63684 KB |
Output is correct |
21 |
Correct |
256 ms |
62556 KB |
Output is correct |
22 |
Correct |
263 ms |
62536 KB |
Output is correct |
23 |
Correct |
315 ms |
62640 KB |
Output is correct |
24 |
Correct |
281 ms |
64716 KB |
Output is correct |
25 |
Correct |
319 ms |
67760 KB |
Output is correct |
26 |
Correct |
262 ms |
62740 KB |
Output is correct |
27 |
Correct |
277 ms |
62688 KB |
Output is correct |
28 |
Correct |
272 ms |
62812 KB |
Output is correct |
29 |
Correct |
327 ms |
64320 KB |
Output is correct |
30 |
Correct |
317 ms |
65780 KB |
Output is correct |
31 |
Correct |
297 ms |
62712 KB |
Output is correct |
32 |
Correct |
261 ms |
62604 KB |
Output is correct |
33 |
Correct |
304 ms |
62900 KB |
Output is correct |
34 |
Correct |
284 ms |
64784 KB |
Output is correct |
35 |
Correct |
338 ms |
67736 KB |
Output is correct |
36 |
Correct |
308 ms |
64740 KB |
Output is correct |