제출 #144305

#제출 시각아이디문제언어결과실행 시간메모리
144305EvirirValley (BOI19_valley)C++17
23 / 100
232 ms20472 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define watch(x) cout<<(#x)<<"="<<(x)<<endl #define mset(d,val) memset(d,val,sizeof(d)) #define setp(x) cout<<fixed<<setprecision(x) #define forn(i,a,b) for(int i=a;i<b;i++) #define fore(i,a,b) for(int i=a;i<=b;i++) #define pb push_back #define F first #define S second #define PI 3.14159265358979323846264338327 #define INF 2e14 #define MOD 998244353 #define pqueue priority_queue #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<int,ll> ii; typedef vector<ll> vi; typedef vector<ii> vii; typedef unsigned long long ull; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; #define MAXN 100005 #define LG 18 int n,s,q,e; bool shop[MAXN]; vii adj[MAXN]; ii edges[MAXN]; int depth[MAXN],prt[MAXN][LG+1]; void dfs_prt(int u,int p){ prt[u][0]=p; forn(j,1,LG){ if(prt[u][j-1]!=-1) prt[u][j]=prt[prt[u][j-1]][j-1]; } for(ii tmp: adj[u]){ int v=tmp.F; if(v==p) continue; depth[v]=depth[u]+1; dfs_prt(v,u); } } ll dist[MAXN]; void dfs(int u,int p,int xu,int xv){ for(ii tmp: adj[u]){ int v=tmp.F; ll w=tmp.S; if(v==p) continue; if((u==xu&&v==xv)||(u==xv&&v==xu)) continue; dist[v]=dist[u]+w; dfs(v,u,xu,xv); } } bool findprt(int u,int v){ for(int i=LG-1;i>=0;i--){ if(prt[u][i]!=-1&&depth[prt[u][i]]>=depth[v]) u=prt[u][i]; } return u==v; } void S2() { forn(it,0,q) { int xe,b; cin>>xe>>b; xe--; b--; int xu=edges[xe].F, xv=edges[xe].S; forn(i,0,n) dist[i]=INF; dist[b]=0; dfs(b,-1,xu,xv); ll minn = INF; forn(i,0,n){ if(shop[i]) minn=min(minn,dist[i]); } if(dist[e]<INF) cout<<"escaped"<<'\n'; else if(minn<INF) cout<<minn<<'\n'; else cout<<"oo"<<'\n'; } } void S3() { forn(it,0,q) { int xe,b; cin>>xe>>b; xe--; b--; int xu=edges[xe].F,xv=edges[xe].S; if(depth[xu]<depth[xv]) swap(xu,xv); //xu is the lower end if(depth[b]<depth[xu]){ cout<<"escaped"<<'\n'; continue; } if(depth[b]==depth[xu]){ if(b==xu) cout<<0<<'\n'; else cout<<"escaped"<<'\n'; continue; } if(findprt(b,xu)) cout<<0<<'\n'; else cout<<"escaped"<<'\n'; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); mset(prt,-1); cin>>n>>s>>q>>e; e--; forn(i,0,n-1){ int u,v; ll w; cin>>u>>v>>w; u--; v--; adj[u].pb({v,w}); adj[v].pb({u,w}); edges[i]={u,v}; } forn(i,0,s){ int u; cin>>u; u--; shop[u]=true; } dfs_prt(e,-1); if(n<=1000&&q<=1000) S2(); else S3(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...