#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
#define mid (l+r)/2
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1000000007;
const ll inf=1e18*4;
const ld pai=acos(-1);
ll n,s,q,root;
ll timer;
vpll v[100009];
pll e[100009];
ll shop[100009];
ll jumpnode[100009][20],jumpmagic[100009][20],magic[100009];
ll depth[100009],st[100009],en[100009],w[100009];
void dfs_calc(int node,int p,ll t){
depth[node]=t;
w[node]=w[p]+1;
st[node]=timer++;
for(auto u:v[node]){
if(u.fi!=p)dfs_calc(u.fi,node,t+u.se);
}
en[node]=timer-1;
}
void dfs_magic(int node,int p){
if(shop[node])magic[node]=depth[node];
else magic[node]=inf;
for(auto u:v[node]){
if(u.fi!=p){
dfs_magic(u.fi,node);
magic[node]=min(magic[node],magic[u.fi]);
}
}
}
void fill_magic(){
for(int i=0;i<n;i++)magic[i]-=2*depth[i];
}
void dfs_lca(int node,int p){
jumpnode[node][0]=p;
jumpmagic[node][0]=min(magic[node],magic[p]);
for(auto u:v[node]){
if(u.fi!=p)dfs_lca(u.fi,node);
}
}
void fill_lca(){
for(int j=1;j<20;j++){
for(int i=0;i<n;i++){
jumpnode[i][j]=jumpnode[jumpnode[i][j-1]][j-1];
jumpmagic[i][j]=min(jumpmagic[jumpnode[i][j-1]][j-1],jumpmagic[i][j-1]);
}
}
}
int check(int a,int b,int x){
if(w[a]<w[b])swap(a,b);
return (st[a]<=st[x] && en[a]>=st[x]);
}
ll solve(int u,int p){
int l=w[u]-w[p];
ll mn=inf;
for(int i=0;i<20;i++){
if((l&(1<<i))){
mn=min(mn,jumpmagic[u][i]);
u=jumpnode[u][i];
}
}
return min(mn,magic[p]);
}
int main(){
cin>>n>>s>>q>>root;
root--;
for(int i=0;i<n;i++){
for(int j=0;j<20;j++)jumpnode[i][j]=root,jumpmagic[i][j]=inf;
}
for(int i=0;i<n-1;i++){
ll a,b,c;cin>>a>>b>>c,a--,b--;
e[i]={a,b};
v[a].pb({b,c});
v[b].pb({a,c});
}
for(int i=0;i<s;i++){
int x;cin>>x,x--;
shop[x]=1;
}
dfs_calc(root,root,0);
dfs_magic(root,root),fill_magic();
dfs_lca(root,root);fill_lca();
while(q--){
int id,node;
cin>>id>>node,id--,node--;
int a=e[id].fi,b=e[id].se;
if(!check(a,b,node))cout<<"escaped"<<endl;
else{
int xxx=-1;
if(w[a]>w[b])xxx=a;
else xxx=b;
ll ans=depth[node]+solve(node,xxx);
if(ans>1e17)cout<<"oo"<<endl;
else cout<<ans<<endl;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
2808 KB |
Output is correct |
2 |
Correct |
37 ms |
2936 KB |
Output is correct |
3 |
Correct |
39 ms |
2936 KB |
Output is correct |
4 |
Correct |
40 ms |
2936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
2808 KB |
Output is correct |
2 |
Correct |
37 ms |
2936 KB |
Output is correct |
3 |
Correct |
39 ms |
2936 KB |
Output is correct |
4 |
Correct |
40 ms |
2936 KB |
Output is correct |
5 |
Correct |
10 ms |
3192 KB |
Output is correct |
6 |
Correct |
11 ms |
3192 KB |
Output is correct |
7 |
Correct |
10 ms |
3192 KB |
Output is correct |
8 |
Correct |
11 ms |
3192 KB |
Output is correct |
9 |
Correct |
11 ms |
3192 KB |
Output is correct |
10 |
Correct |
15 ms |
3192 KB |
Output is correct |
11 |
Correct |
10 ms |
3196 KB |
Output is correct |
12 |
Correct |
10 ms |
3192 KB |
Output is correct |
13 |
Correct |
10 ms |
3192 KB |
Output is correct |
14 |
Correct |
9 ms |
3192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
756 ms |
46184 KB |
Output is correct |
2 |
Correct |
778 ms |
46008 KB |
Output is correct |
3 |
Correct |
796 ms |
46200 KB |
Output is correct |
4 |
Correct |
854 ms |
47608 KB |
Output is correct |
5 |
Correct |
812 ms |
47864 KB |
Output is correct |
6 |
Correct |
846 ms |
49764 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
2808 KB |
Output is correct |
2 |
Correct |
37 ms |
2936 KB |
Output is correct |
3 |
Correct |
39 ms |
2936 KB |
Output is correct |
4 |
Correct |
40 ms |
2936 KB |
Output is correct |
5 |
Correct |
10 ms |
3192 KB |
Output is correct |
6 |
Correct |
11 ms |
3192 KB |
Output is correct |
7 |
Correct |
10 ms |
3192 KB |
Output is correct |
8 |
Correct |
11 ms |
3192 KB |
Output is correct |
9 |
Correct |
11 ms |
3192 KB |
Output is correct |
10 |
Correct |
15 ms |
3192 KB |
Output is correct |
11 |
Correct |
10 ms |
3196 KB |
Output is correct |
12 |
Correct |
10 ms |
3192 KB |
Output is correct |
13 |
Correct |
10 ms |
3192 KB |
Output is correct |
14 |
Correct |
9 ms |
3192 KB |
Output is correct |
15 |
Correct |
756 ms |
46184 KB |
Output is correct |
16 |
Correct |
778 ms |
46008 KB |
Output is correct |
17 |
Correct |
796 ms |
46200 KB |
Output is correct |
18 |
Correct |
854 ms |
47608 KB |
Output is correct |
19 |
Correct |
812 ms |
47864 KB |
Output is correct |
20 |
Correct |
846 ms |
49764 KB |
Output is correct |
21 |
Correct |
747 ms |
48888 KB |
Output is correct |
22 |
Correct |
741 ms |
48612 KB |
Output is correct |
23 |
Correct |
826 ms |
48828 KB |
Output is correct |
24 |
Correct |
764 ms |
50452 KB |
Output is correct |
25 |
Correct |
809 ms |
52916 KB |
Output is correct |
26 |
Correct |
709 ms |
48952 KB |
Output is correct |
27 |
Correct |
724 ms |
48916 KB |
Output is correct |
28 |
Correct |
747 ms |
49016 KB |
Output is correct |
29 |
Correct |
767 ms |
50296 KB |
Output is correct |
30 |
Correct |
822 ms |
51704 KB |
Output is correct |
31 |
Correct |
732 ms |
49660 KB |
Output is correct |
32 |
Correct |
758 ms |
49412 KB |
Output is correct |
33 |
Correct |
779 ms |
49600 KB |
Output is correct |
34 |
Correct |
807 ms |
51212 KB |
Output is correct |
35 |
Correct |
801 ms |
53540 KB |
Output is correct |
36 |
Correct |
759 ms |
51048 KB |
Output is correct |