Submission #1104718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104718		ToTenLinh	Valley (BOI19_valley)	C++17	100 / 100	117 ms	47432 KiB

valley

#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;
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41