제출 #154976

#제출 시각아이디문제언어결과실행 시간메모리
154976GoldNextYearValley (BOI19_valley)C++14
0 / 100
788 ms48480 KiB
#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; vpi v[100009]; pi 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,int 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 a,int b){ ll l=w[a]-w[b]; ll mn=inf; for(int i=0;i<20;i++){ if((l&(1<<i))){ mn=min(mn,jumpmagic[a][i]); a=jumpnode[a][i]; } } return mn; } int main(){ cin>>n>>s>>q>>root; root--; 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>inf-1)cout<<"oo"<<endl; else cout<<ans<<endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...