#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<cmath>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pb push_back
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
//#define int long long
#define mod 1000000007
#define int long long
const int mxn=1e5,lg=17,inf=1e18;
vector<pii>adj[mxn+10];
vector<int>shop;
vector<pair<pii,int>>edge;
int up[mxn+10][20],h[mxn+10],sdist[mxn+10],dist[mxn+10];
int dp[mxn+10][20];
void solve(int cur,int p){
for(auto i:adj[cur]){
if(i.f==p)continue;
h[i.f]=h[cur]+1;
up[i.f][0]=cur;
dist[i.f]=dist[cur]+i.s;
solve(i.f,cur);
sdist[cur]=min(sdist[cur],sdist[i.f]+i.s);
}
dp[cur][0]=sdist[cur];
}
int caldist(int a,int b){return abs(dist[a]-dist[b]);}
int cal(int node,int k){
int ans=inf,d=0;
for(int i=0;i<=lg;i++){
if(k&(1<<i)){
ans=min(ans,dp[node][i]+d);
d+=abs(dist[node]-dist[up[node][i]]);
node=up[node][i];
}
}
return ans;
}
int32_t main(){
fastio
int n,m,q,e;cin>>n>>m>>q>>e;
for(int i=0;i<n-1;i++){
int u,v,w;cin>>u>>v>>w;
adj[u].pb({v,w});
adj[v].pb({u,w});
edge.pb({{u,v},w});
}
fill(sdist,sdist+n+1,inf);
for(int i=1;i<=lg;i++)for(int j=1;j<=n;j++)dp[j][i]=inf;
for(int i=0;i<m;i++){
int a;cin>>a;
sdist[a]=0;
}
solve(e,-1);
for(int i=1;i<=lg;i++){
for(int j=1;j<=n;j++){
up[j][i]=up[up[j][i-1]][i-1];
dp[j][i]=min(dp[j][i-1],abs(dist[j]-dist[up[j][i-1]])+dp[up[j][i-1]][i-1]);
}
}
while(q--){
int a,b;cin>>a>>b;
a--;
if(h[edge[a].f.f]>h[edge[a].f.s])a=edge[a].f.f;
else a=edge[a].f.s;
if(h[a]<=h[b]){
int cur=b;
int k=h[b]-h[a];
for(int i=0;i<=lg;i++)if(k&(1<<i))cur=up[cur][i];
if(cur==a){
int k=h[b]-h[a]+1;
int g=cal(b,k);
if(g!=inf)cout<<g<<'\n';
else cout<<"oo"<<'\n';
}
else cout<<"escaped"<<'\n';
}
else cout<<"escaped"<<'\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2772 KB |
Output is correct |
2 |
Correct |
3 ms |
2772 KB |
Output is correct |
3 |
Correct |
3 ms |
2812 KB |
Output is correct |
4 |
Correct |
3 ms |
2772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2772 KB |
Output is correct |
2 |
Correct |
3 ms |
2772 KB |
Output is correct |
3 |
Correct |
3 ms |
2812 KB |
Output is correct |
4 |
Correct |
3 ms |
2772 KB |
Output is correct |
5 |
Correct |
2 ms |
3136 KB |
Output is correct |
6 |
Correct |
2 ms |
3068 KB |
Output is correct |
7 |
Correct |
2 ms |
3072 KB |
Output is correct |
8 |
Correct |
3 ms |
3028 KB |
Output is correct |
9 |
Correct |
2 ms |
3072 KB |
Output is correct |
10 |
Correct |
2 ms |
3028 KB |
Output is correct |
11 |
Correct |
2 ms |
3028 KB |
Output is correct |
12 |
Correct |
2 ms |
3028 KB |
Output is correct |
13 |
Correct |
2 ms |
3068 KB |
Output is correct |
14 |
Correct |
2 ms |
3156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
134 ms |
48316 KB |
Output is correct |
2 |
Correct |
152 ms |
48116 KB |
Output is correct |
3 |
Correct |
173 ms |
48396 KB |
Output is correct |
4 |
Correct |
172 ms |
50200 KB |
Output is correct |
5 |
Correct |
162 ms |
50304 KB |
Output is correct |
6 |
Correct |
220 ms |
52508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2772 KB |
Output is correct |
2 |
Correct |
3 ms |
2772 KB |
Output is correct |
3 |
Correct |
3 ms |
2812 KB |
Output is correct |
4 |
Correct |
3 ms |
2772 KB |
Output is correct |
5 |
Correct |
2 ms |
3136 KB |
Output is correct |
6 |
Correct |
2 ms |
3068 KB |
Output is correct |
7 |
Correct |
2 ms |
3072 KB |
Output is correct |
8 |
Correct |
3 ms |
3028 KB |
Output is correct |
9 |
Correct |
2 ms |
3072 KB |
Output is correct |
10 |
Correct |
2 ms |
3028 KB |
Output is correct |
11 |
Correct |
2 ms |
3028 KB |
Output is correct |
12 |
Correct |
2 ms |
3028 KB |
Output is correct |
13 |
Correct |
2 ms |
3068 KB |
Output is correct |
14 |
Correct |
2 ms |
3156 KB |
Output is correct |
15 |
Correct |
134 ms |
48316 KB |
Output is correct |
16 |
Correct |
152 ms |
48116 KB |
Output is correct |
17 |
Correct |
173 ms |
48396 KB |
Output is correct |
18 |
Correct |
172 ms |
50200 KB |
Output is correct |
19 |
Correct |
162 ms |
50304 KB |
Output is correct |
20 |
Correct |
220 ms |
52508 KB |
Output is correct |
21 |
Correct |
125 ms |
47736 KB |
Output is correct |
22 |
Correct |
137 ms |
47508 KB |
Output is correct |
23 |
Correct |
149 ms |
47728 KB |
Output is correct |
24 |
Correct |
162 ms |
49908 KB |
Output is correct |
25 |
Correct |
167 ms |
52904 KB |
Output is correct |
26 |
Correct |
126 ms |
47708 KB |
Output is correct |
27 |
Correct |
141 ms |
47532 KB |
Output is correct |
28 |
Correct |
145 ms |
47824 KB |
Output is correct |
29 |
Correct |
177 ms |
49232 KB |
Output is correct |
30 |
Correct |
197 ms |
50936 KB |
Output is correct |
31 |
Correct |
127 ms |
47820 KB |
Output is correct |
32 |
Correct |
138 ms |
47736 KB |
Output is correct |
33 |
Correct |
158 ms |
47992 KB |
Output is correct |
34 |
Correct |
174 ms |
49868 KB |
Output is correct |
35 |
Correct |
183 ms |
52760 KB |
Output is correct |
36 |
Correct |
149 ms |
49844 KB |
Output is correct |