제출 #958706

#제출 시각아이디문제언어결과실행 시간메모리
958706YassirSalamaValley (BOI19_valley)C++17
0 / 100
3044 ms41076 KiB
#include <bits/stdc++.h> using namespace std; const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; #define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n"; #ifdef IOI void dbg_out() { cout << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); } #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__); #else #define dbg(...) 1337; #endif #define endl "\n" #define pb push_back #define F first #define S second #define ll long long #define mod 1000000007 #define all(v) v.begin(),v.end() #define int long long const int MAXN=2e5+100; const int LOGN=20; int up[MAXN][LOGN+1]; vector<pair<int,int>> v[MAXN]; vector<vector<int>> ed; int depth1[MAXN]; int depth2[MAXN]; int tin[MAXN]; int tout[MAXN]; int t=1; void dfs(int node,int par=0){ tin[node]=t++; depth1[node]=depth1[par]+1; up[node][0]=par; for(int i=1;i<=LOGN;i++) up[node][i]=up[up[node][i-1]][i-1]; for(auto x:v[node]){ if(x.F==par) continue; depth2[x.F]=depth2[node]+x.S; dfs(x.F,node); } tout[node]=t++; } bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } int LCA(int a,int b){ if(depth1[a]<depth1[b]) swap(a,b); int d=depth1[a]-depth1[b]; for(int i=LOGN;i>=0;i--){ if((1LL<<i)&d){ a=up[a][i]; } } if(a==b) return a; for(int i=LOGN;i>=0;i--){ if(up[a][i]!=up[b][i]){ a=up[a][i]; b=up[b][i]; } } return up[a][0]; } vector<int> sh; signed main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); int n,s,q,e; cin>>n>>s>>q>>e; for(int i=1;i<n;i++){ int a,b; int c; cin>>a>>b>>c; ed.pb({a,b}); v[a].pb(make_pair(b,c)); v[b].pb(make_pair(a,c)); } dfs(e); for(int i=0;i<s;i++){ int sx; cin>>sx; sh.pb(sx); } for(int i=0;i<q;i++){ int p,r; cin>>p>>r; p--; int a=ed[p][0],b=ed[p][1]; // dbg(a,b,LCA(r,a),LCA(r,b)) if(!(is_ancestor(a,r)&&is_ancestor(b,r))){ cout<<"escaped"<<endl; continue; } int ans=1e18; for(auto y:sh){ int x=y; // dbg(x) int l=LCA(r,x); if(is_ancestor(a,r)&&is_ancestor(b,r)&&is_ancestor(l,a)&&is_ancestor(l,b)){ continue; } if(is_ancestor(a,x)&&is_ancestor(b,x)&&is_ancestor(l,a)&&is_ancestor(l,b)){ continue; } ans=min(ans,depth2[x]+depth2[r]-2*depth2[l]); } if(ans==1e18){ cout<<"oo"<<endl; continue; } cout<<0<<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...