Submission #1104718

#TimeUsernameProblemLanguageResultExecution timeMemory
1104718ToTenLinhValley (BOI19_valley)C++17
100 / 100
117 ms47432 KiB
#include <bits/stdc++.h> #define fo(i,m,n) for(int i=m;i<=n;i++) #define fod(i,n,m) for(int i=n;i>=m;i--) #define fo1(i,m,n,k) for(int i=m;i<=n;i=i+k) #define fod1(i,n,m,k) for(int i=n;i>=m;i=i-k) #define fol(i,m,n) for(long long i=m;i<=n;i++) #define fodl(i,n,m) for(long long i=n;i>=m;i--) #define fo1l(i,m,n,k) for(long long i=m;i<=n;i=i+k) #define fod1l(i,n,m,k) for(long long i=n;i>=m;i=i-k) #define lb lower_bound #define ub upper_bound #define pii pair <int,int> #define vii vector<pii> #define ll long long #define fi first #define se second #define si size() #define pb push_back #define ppb pop_back() #define fr front() #define et empty() #define bg begin() #define ub upper_bound #define lb lower_bound #define ed end() #define el endl #define EL cout << '\n'; using namespace std; const int mod = 1e9 + 7; const int N = 1e5 + 5; const int M = 1e3 + 5; vii adj[N]; pii canh[N]; bool isa[N]= {false}; ll depth[N] = {0}, len[N] = {0}, m[N] = {(ll)1e18}, f[20][N], dp[20][N]; int st[N], en[N], p[N], t = 0; void dfs(int u, int par){ st[u] = t; t ++; p[u] = par; for(pii it : adj[u]){ int v = it.fi, val = it.se; if(v == par) continue; depth[v] = depth[u] + 1; len[v] = len[u] + val; dfs(v, u); } en[u] = t; t ++; } void dfs2(int u, int par){ if(isa[u]) m[u] = len[u]; else m[u] = (ll)1e18; for(pii it : adj[u]){ int v = it.fi; if(v == par) continue; dfs2(v, u); m[u] = min(m[u], m[v]); } } ll query(int top, int node){ int x = node; int plen = depth[node] - depth[top]; ll ans = m[node]; fo(i, 0, 19){ if(plen & (1<<i)){ ans = min(ans, dp[i][node]); node = f[i][node]; } } return ans + len[x]; } void solve(){ int n, s, q, e; cin>> n >> s >> q >> e; fo(i, 1, n - 1){ int u, v, val; cin>> u >> v >> val; adj[u].pb({v, val}); adj[v].pb({u, val}); canh[i]={u, v}; } fo(i, 1, s){ int x; cin >> x; isa[x] = true; } dfs(e, 0); dfs2(e, 0); fo(i, 1, n) m[i] -= 2 * len[i]; fo(i, 1, n){ f[0][i] = p[i]; dp[0][i] = m[p[i]]; } fo(i, 1, 19){ fo(j, 1, n){ f[i][j] = f[i - 1][f[i - 1][j]]; dp[i][j] = min(dp[i - 1][j], dp[i - 1][f[i - 1][j]]); } } while(q --){ int edge, node; cin>> edge >> node; int top = (depth[canh[edge].fi] > depth[canh[edge].se] ? canh[edge].fi : canh[edge].se); if(st[top] <= st[node] && en[node] <= en[top]){ if(query(top, node) <= (ll)1e14) cout << query(top, node) << '\n'; else cout << "oo\n"; } else cout << "escaped\n"; } } signed main() { // freopen("LANDSLIDE.inp","r",stdin); // freopen("LANDSLIDE.out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); 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...