Submission #1182204

#TimeUsernameProblemLanguageResultExecution timeMemory
1182204MatbubbleValley (BOI19_valley)C++20
100 / 100
140 ms52076 KiB
#include <iostream> #include <iomanip> #include <string> #include <math.h> #include <algorithm> #include <cstring> #include <numeric> #include <vector> #include <bitset> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <unordered_map> #include <unordered_set> using namespace std; #define dbg(x) cerr<<#x<<": "<<x<<"\n"; /* xdxd */ const long long maxN=1e5; vector<pair<long long, long>>g[maxN+1]; bool tienda[maxN+1]; long long min_dis[maxN+1]; long long dis[maxN+1]; long long bl[maxN+1][21]; long long dp[maxN+1][21]; long long tin[maxN+1], tout[maxN+1], depth[maxN+1]; long long cont=0; void dfs(long long u, long long root){ long long mini=1e18; if(tienda[u]==1) mini=0; bl[u][0]=root; for(long long i=1 ; i<20 ; i++){ bl[u][i]=bl[bl[u][i-1]][i-1]; } // dbg(cont) tin[u]=++cont; for(auto v:g[u]){ if(v.first==root) continue; dis[v.first]=dis[u]+v.second; depth[v.first]=depth[u]+1; dfs(v.first, u); mini=min(mini, min_dis[v.first]+v.second); } tout[u]=++cont; min_dis[u]=mini; } bool papi(long long u, long long v){ return tin[u]<=tin[v] && tout[u]>=tout[v]; } long long lca(long long u, long long v){ // dbg("pene") if(papi(u, v)) return u; if(papi(v, u)) return v; for(long long l=19 ; l>=0 ; l--){ // dbg(l) if(papi(bl[u][l], v)==false){ u=bl[u][l]; } } return bl[u][0]; } long long distancia(long long u, long long v){ return dis[v]-dis[u]; } void pre(long long u, long long root){ dp[u][0]=min(min_dis[u], min_dis[root]+distancia(root, u)); for(long long l=1 ; l<20 ; l++){ dp[u][l]=min(dp[u][l-1], dp[bl[u][l-1]][l-1]+distancia(bl[u][l-1], u)); } for(auto v:g[u]){ if(v.first==root) continue; pre(v.first, u); } } void solve(){ long long n, s, q, e; cin>>n>>s>>q>>e; vector<pair<long long, long long>>adj; for(long long i=1 ; i<n ; i++){ long long a, b, w; cin>>a>>b>>w; g[a].push_back({b, w}); g[b].push_back({a, w}); adj.push_back({a, b}); } for(long long i=0 ; i<s ; i++){ long long a; cin>>a; tienda[a]=1; } for(long long i=0 ; i<=n ; i++){ for(long long j=0 ; j<20 ; j++) bl[i][j]=e; } for(long long i=0 ; i<=n ; i++){ for(long long j=0 ; j<20 ; j++) dp[i][j]=0; } dis[e]=0; depth[e]=0; dfs(e, e); pre(e, e); // for(long long i=0 ; i<=n ; i++){ // for(long long j=0 ; j<20 ; j++) cout<<dp[i][j]<<" "; // cout<<"\n"; // } // for(long long i=1 ; i<=n ; ?i++) dbg(min_dis[i]) while(q--){ long long I, R; cin>>I>>R; I--; long long one=adj[I].first, two=adj[I].second; if(depth[two]>depth[one]) swap(one, two); if(lca(one, R)==one){ long long xd=R; long long init=min_dis[R]; // dbg(min_dis[R]); for(long long l=19 ; l>=0 ; l--){ if(papi(bl[R][l], one)==false || bl[R][l]==one){ // dbg(R) // dbg(l) // dbg(one) // dbg(bl[R][l]) // dbg("----")¢ init=min(init, distancia(R, xd)+dp[R][l]); R=bl[R][l]; } } if(init==1e18) cout<<"oo\n"; else cout<<init<<"\n"; }else{ cout<<"escaped\n"; } } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); 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...