Submission #704590

#TimeUsernameProblemLanguageResultExecution timeMemory
704590hoangnghiepValley (BOI19_valley)C++14
23 / 100
291 ms68144 KiB
#include<bits/stdc++.h> #define int long long #define f first #define s second #define repeat(i,a,b) for(int i=a;i<=b;i++) #define pb push_back #define p push #define pii pair<int,int> #define piii pair<int,pair<int,int>> #define vii vector<vector<int>> #define vi vector<int> //#define DEBUG //#define multipletest using namespace std; const int LIM=1e5; const int mod=1e9+7; const int maxn=20; const int inf=1e9; int n,m,x,y,k,t,e,q,s; int dx[8]={1,-1,0,0,-1,-1,1,1}; int dy[8]={0,0,-1,1,1,-1,1,-1}; char c; int a[LIM+5],factorial[(1<<maxn)+5],inv_fact[(1<<maxn)+5]; bool notprime[LIM+5]; vector<pii> adj[LIM+5]; map<int,int> mp; char grid[100+5][100+5]; int power(int a,int b){ if(b==0) return 1; int t=power(a,b/2); t = t * t %mod; if(b%2==1) t = t * a %mod; return t; } bool check(int x,int y){ if(x<=0 || x>n || y<=0 || y>m || grid[x][y]=='T'){ return false; } return true; } class DSU{ int *parent; int *rank; int *tot; public: DSU(int n){ rank=new int[n+5]; parent=new int[n+5]; tot=new int [n+5]; for(int i=0;i<n+5;i++){ parent[i]=i; rank[i]=0; tot[i]=1; } } int find(int i){ if(parent[i]==i){ return i; } return parent[i]=find(parent[i]); } void unite(int u,int v){ int i=find(u); int j=find(v); if(i!=j){ if(rank[i]>rank[j]){ parent[j]=i; tot[i]+=tot[j]; } else if(rank[i]<rank[j]){ parent[i]=j; tot[j]+=tot[i]; } else{ parent[j]=i; rank[i]++; tot[i]+=tot[j]; } } } int total(int u){ return tot[u]; } }; void precal(int n){ factorial[0]=1; inv_fact[0]=1; for (int i = 1; i <n; ++i) { factorial[i] = factorial[i - 1] * i % mod; inv_fact[i] = inv_fact[i - 1] * power(i, mod - 2) % mod; } } int choose(int n,int k){ if(k<0 || k>n) return 0; return factorial[n] * inv_fact[n-k] % mod * inv_fact[k] %mod; } void Sieve(){ notprime[0]=notprime[1]=true; for(int i=2;i<LIM+5;++i){ if(notprime[i]==false){ for(int j=i*i;j<LIM+5;j+=i){ notprime[j]=true; } } } } bool shop[LIM+5]; int tail[LIM+5]; int depth[LIM+5],disc[LIM+5],dp[LIM+5],low[LIM+5]; int up[20][LIM+5]; int updist[20][LIM+5]; int upshop[20][LIM+5]; pii edges[LIM+5]; int timedfs=0; void dfs(int u,int parent){ disc[u]=++timedfs; up[0][u]=parent; for(auto to:adj[u]){ if(to.f!=parent){ int v=to.f; int w=to.s; depth[v]=depth[u]+1; dfs(v,u); updist[0][v]=w; dp[u]=min(dp[u],(dp[v]==inf?inf:dp[v]+w)); } } tail[u]=timedfs; } void solve(){ //Sieve(); // precal(); cin>>n>>s>>q>>e; for(int i=1;i<=n-1;++i){ int u,v,w; cin>>u>>v>>w; adj[u].push_back({v,w}); adj[v].push_back({u,w}); edges[i].f=u,edges[i].s=v; } for(int i=1;i<=n;++i){ dp[i]=inf; } for(int i=0;i<s;++i){ int u; cin>>u; dp[u]=0; } dfs(e,e); for(int i=0;i<20;++i){ upshop[i][e]=dp[e]; } for(int i=1;i<=n;++i){ upshop[0][i]=dp[i]; } // cout<<dp[e]<<endl; for(int i=1;i<20;++i){ for(int j=1;j<=n;++j){ up[i][j]=up[i-1][up[i-1][j]]; updist[i][j]=updist[i-1][j] + updist[i-1][up[i-1][j]]; upshop[i][j]=min(upshop[i-1][j],updist[i-1][j] + upshop[i-1][up[i-1][j]] ); } } // for(int i=1;i<20;++i){ // for(int j=1;j<=n;++j){ // cout<<upshop[i][j] <<" "; // } // cout<<endl; // } while(q--){ int id,vertex; cin>>id>>vertex; int u=edges[id].f,v=edges[id].s; // cout<<depth[u]<<" "<<depth[v]<<endl; if(depth[u]>depth[v]){ swap(u,v); } if(disc[v]<=disc[vertex] && tail[v]>=tail[vertex]){ int ans=inf; int jump= depth[vertex]-depth[u]; int temp=0,path=0; while(jump>0){ if(jump%2==1){ ans = min(ans , (upshop[temp][vertex]==inf?inf : path + upshop[temp][vertex])); path+=updist[temp][vertex]; vertex = up[temp][vertex]; } jump>>=1; temp++; } if(ans==inf) cout<<"oo"<<endl; else cout<<ans<<endl; } else{ cout<<"escaped"<<endl; } } } signed main(){ // freopen(".inp","r",stdin); // freopen(".out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); int test; test=1; #ifdef multipletest cin>>test; #endif while(test--){ solve(); #ifdef DEBUG cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl; #endif } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...