제출 #258734

#제출 시각아이디문제언어결과실행 시간메모리
258734anubhavdharValley (BOI19_valley)C++14
0 / 100
546 ms34028 KiB
#include<bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define pii pair<int, int> #define pll pair<ll, ll> #define ff first #define ss second #define vi vector<int> #define vl vector<ll> #define vii vector<pii> #define vll vector<pll> #define FOR(i,N) for(i=0;i<(N);++i) #define FORe(i,N) for(i=1;i<=(N);++i) #define FORr(i,a,b) for(i=(a);i<(b);++i) #define FORrev(i,N) for(i=(N);i>=0;--i) #define F0R(i,N) for(int i=0;i<(N);++i) #define F0Re(i,N) for(int i=1;i<=(N);++i) #define F0Rr(i,a,b) for(ll i=(a);i<(b);++i) #define F0Rrev(i,N) for(int i=(N);i>=0;--i) #define all(v) (v).begin(),(v).end() #define dbgLine cerr<<" LINE : "<<__LINE__<<"\n" #define ldd long double using namespace std; const int Alp = 26; const int __PRECISION = 9; const int inf = 1e9 + 8; const ldd PI = acos(-1); const ldd EPS = 1e-7; const ll MOD = 1e9 + 7; const ll MAXN = 1e5 + 5; const ll ROOTN = 320; const ll LOGN = 18; const ll INF = 1e18 + 1022; int N, Q, E, S, CLK, xt[MAXN], nt[MAXN], par[LOGN][MAXN], depcnt[MAXN]; ll dp[MAXN], sparse[LOGN][MAXN], dep[MAXN]; bool shop[MAXN]; vector<pair<int, ll>> g[MAXN]; vector<pair<pii, ll>> edge_list; ll dfs(int a, int pp) { nt[a] = CLK++; par[0][a] = pp; for(pair<int, ll> b : g[a]) if(b.ff != pp) { dep[b.ff] = b.ss + dep[a]; depcnt[b.ff] = 1 + dep[a]; dp[a] = min(dp[a], dfs(b.ff, a) + b.ss); } if(shop[a]) dp[a] = 0; for(pair<int, ll> b : g[a]) if(b.ff != pp) { // cerr<<"sparse[0]["<<b.ff<<"] = "<<min(sparse[0][b.ff], b.ss + dp[a])<<'\n'; sparse[0][b.ff] = min(sparse[0][b.ff], b.ss + dp[a]); } xt[a] = CLK++; return dp[a]; } inline void init_sparse_table() { F0Re(i, LOGN-1) F0Re(a, N) par[i][a] = (par[i-1][a] == -1) ? -1 : par[i-1][par[i-1][a]], sparse[i][a] = min(sparse[i-1][a],(((par[i-1][a]==-1) ? INF : (sparse[i-1][par[i-1][a]] + dep[a] - dep[par[i-1][a]])))); } // inline void dbg_dp() // { // F0Re(i, N) // cout<<"dp["<<i<<"] = "<<dp[i]<<'\n'; // } inline void pre_process() { CLK = 0; dep[E] = depcnt[E] = 0; F0Re(i, N) dp[i] = INF; F0R(i, LOGN) F0Re(a, N) sparse[i][a] = INF; dfs(E, -1); // dbg_dp(); init_sparse_table(); } inline void query(int e, int a) { int u = (depcnt[edge_list[e].ff.ff] > depcnt[edge_list[e].ff.ss]) ? edge_list[e].ff.ff : edge_list[e].ff.ss; if(!(nt[u] <= nt[a] and xt[u] >= xt[a])) { cout<<"escaped\n"; return; } cout<<"0\n";return; int b = a; ll ans = dp[a]; F0Rrev(i, LOGN-1) { if(par[i][b] == -1 or depcnt[par[i][b]] < depcnt[u]) continue; ans = min(ans, sparse[i][b] + dep[a] - dep[b]); // cerr<<"considering "<<par[i][b]<<" and sparse["<<i<<"]["<<b<<"] = "<<sparse[i][b]<<'\n'; b = par[i][b]; } if(ans == INF) cout<<"oo\n"; else cout<<ans<<'\n'; } signed main() { /* ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); */ int j, k; ll len; cin>>N>>S>>Q>>E; F0R(i, N-1) { cin>>j>>k>>len; edge_list.pb(mp(mp(j, k), len)); g[j].pb(mp(k,len)); g[k].pb(mp(j,len)); } F0Re(i, N) shop[i] = false; F0Re(i, S) { cin>>j; shop[j] = true; } // F0Re(i, N) // cerr<<shop[i]<<' '; // cerr<<'\n'; pre_process(); while(Q--) { cin>>j>>k; query(j-1, k); } return 0; } /* 5 2 3 1 1 2 3 1 3 2 3 4 1 3 5 2 2 4 2 2 2 5 4 5 10 2 5 4 7 2 3 4 8 3 9 10 1 6 7 3 9 2 3 10 1 2 8 2 2 5 2 1 3 8 2 8 7 2 1 1 5 8 4 6 2 7 7 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...