Submission #1003015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003015		tien_07	Valley (BOI19_valley)	C++17	100 / 100	111 ms	43088 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define ms(a,n) memset(a,n,sizeof(a))
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,b,a) for(int i = b; i >= a; i--)
//Bit
#define MASK(x) (1ll<<(x))
#define BIT(mask, i) (((mask) >> (i))&1)
#define SET_ON(x,i) ((x) | MASK(i))
#define SET_OFF(x,i) ((x) & ~MASK(i))
#define c_bit(i) __builtin_popcountll(i)
#define TASK "test"

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef pair<double,double> dd;
typedef vector<ll> vll;
typedef vector<int> vi;

inline ll gcd(ll a, ll b){return b==0 ? a : gcd(b,a%b);}
inline ll lcm(ll a, ll b){return a/gcd(a,b)*b;}

const ld PI = 3.141592653589793238462643383279502884L;
const int MOD = 1e9+7;
const ll LINF = 1e18;
const int INF = 1e9;
const int N = 1e5+5;
const int LOG = __lg(N)+5;

int n,s,q,E, a[N], l[N], r[N];
int par[N][LOG], h[N];
ll dis[N], MIN[N][LOG];
vector<iii> edge(N);
vector<ii> g[N];

int timer = 0;
void dfs(int u, int p){
    l[u] = ++timer;
    for(auto &[v,w] : g[u]){
        if(v==p) continue;
        dis[v] = dis[u] + w;
        h[v] = h[u] + 1;
        dfs(v,u);
        par[v][0] = u;
    }
    r[u] = ++timer;
}

void cal(int u, int p){
    for(auto &[v,w] : g[u]){
        if(v==p) continue;
        cal(v,u);
    }

    if(a[u]) MIN[u][0] = dis[u];
    else MIN[u][0] = LINF;

    for(auto &[v,w] : g[u]){
        if(v==p) continue;
        MIN[u][0] = min(MIN[u][0], MIN[v][0]);
    }
}

int inside(int u, int v){
    return (l[u]<=l[v] && r[v]<=r[u]);
}

ll f(int u, int p){
    ll ans = LINF;
    int len = h[u] - h[p];
    while(len){
        int lim = __lg(len);
        ans = min(ans,MIN[u][lim]);
        u = par[u][lim];
        len -= MASK(lim);
    }
    ans = min(ans,MIN[p][0]);
    return ans;
}

void solve() {
    cin >> n >> s >> q >> E;
    FOR(i,1,n-1){
        int u,v,w; cin >> u >> v >> w;
        edge[i] = {{u,v},w};
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    FOR(i,1,s){
        int u; cin >> u;
        a[u] = 1;
    }

    dfs(E,-1);
    cal(E,-1);
    FOR(i,1,n) MIN[i][0] -= 2*dis[i];

    FOR(j,1,LOG-1){
        FOR(i,1,n){
            par[i][j] = par[par[i][j-1]][j-1];
            MIN[i][j] = min(MIN[i][j-1], MIN[par[i][j-1]][j-1]);
        }
    }


    while(q--){
        int I,R; cin >> I >> R;
        int u = edge[I].fi.fi, v = edge[I].fi.se;
        if(l[u] < l[v]) swap(u,v);

        if(inside(u,R)){
            ll ans = dis[R] + f(R,u);
            if(ans >= (ll)1e15) cout << "oo" << endl;
            else cout << ans << endl;
        }else cout << "escaped" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(TASK ".inp", "r", stdin);
    //freopen(TASK ".out", "w", stdout);
    int tc = 1; //cin >> tc;
    while (tc--) solve();

    return 0;
}

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