Submission #522781

#TimeUsernameProblemLanguageResultExecution timeMemory
522781fadi57Valley (BOI19_valley)C++14
0 / 100
415 ms48840 KiB
#include<bits/stdc++.h> using namespace std; const int mx=2e5+9; typedef long long ll; const int mod=1000000007; const long long inf=1e8+10; const int SQ=450; //typedef int long long; int arr[mx]; int shop[mx]; int tin[mx],tout[mx],depth[mx]; ll cost[mx],mn[20][mx],dp[20][mx],dist[mx]; int tim;int n,s,q,e; vector<pair<int,int>>adj[mx]; int u[mx],v[mx]; void dfs(int node,int par){ tin[node]=tim++; if(shop[node]==1){ cost[node]=0; }else{ cost[node]=inf; } for(auto it:adj[node]){ if(it.first==par){continue;} depth[it.first]=depth[node]+1; dist[it.first]=dist[node]+it.second; dfs(it.first,node); cost[node]=min(cost[node],cost[it.first]+it.second); } tout[node]=tim++; } void dfs2(int node,int par){ dp[0][node]=par; mn[0][node]=cost[par]-dist[par]; for(auto it:adj[node]){ if(it.first==par){continue;} dfs2(it.first,node); } for(int i=1;i<20;i++){ dp[i][node]=dp[i-1][dp[i-1][node]]; mn[i][node]=min(mn[i-1][node],mn[i-1][dp[i-1][node]]); } } bool ok(int x,int y){ if(tin[x]<=tin[y]&&tout[y]<=tout[x]){ return 1; } return 0; } ll calc(int node,int x ){ ll costt=inf; int z=x; for(int i=19;i>=0;i--){ if(depth[dp[i][x]]>=depth[node]){ costt=min(costt,mn[i][x]); x=dp[i][x]; } } return costt; } int main(){ cin>>n>>s>>q>>e; cost[0]=inf; for(int i=0;i<n-1;i++){ int a,b,w; cin>>a>>b>>w; u[i]=a; v[i]=b; adj[a].push_back({b,w}); adj[b].push_back({a,w}); } for(int i=0;i<s;i++){ int x; cin>>x; shop[x]=1; } dfs(1,0); dfs2(1,0); while(q--){ int i,r; cin>>i>>r; i--; int node=v[i]; if(dp[0][u[i]]==v[i]){ node=u[i]; } if(!ok(node,r)){ cout<<"escaped"; }else{ ll ans=calc(node,r); ans=min(ans+dist[r],cost[r]); if(ans>=inf){cout<<"oo";}else{cout<<ans;} //cout<<node<<" "<<ans; } cout<<"\n"; } }

Compilation message (stderr)

valley.cpp: In function 'll calc(int, int)':
valley.cpp:68:13: warning: unused variable 'z' [-Wunused-variable]
   68 |         int z=x;
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...