Submission #1201781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201781		thanhcodedao	Valley (BOI19_valley)	C++20	59 / 100	443 ms	22852 KiB

valley

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

#define F first
#define S second
#define pb push_back
#define checkbit(mask,i) ((mask>>i)&1)
#define bit(i) (1<<i)
#define MLog 18
typedef long long ll;
const ll maxN = 1e5+5, modd = 1e9+7;
vector<pair<ll,ll>> adj[maxN];
int n,s,q,e;
int c[maxN];
int st[maxN],fn[maxN],cnt = 0;
ll d[maxN];
int pa[MLog+1][maxN],h[maxN];
pair<int,int> E[maxN];
void pre_dfs(int u,int par){
    st[u] = ++cnt;
    h[u] = h[par] + 1;
    pa[0][u] = par;
    for(pair<ll,ll> pp : adj[u]){
        ll v = pp.F, w = pp.S;
        if(v==par) continue;
        d[v] = d[u] + w;
        pre_dfs(v,u);
    }
    fn[u] = cnt;
}
void build_lca(){
    for(int i = 1;i<=MLog;i++){
        for(int j = 1;j<=n;j++){
            pa[i][j] = pa[i-1][pa[i-1][j]];
        }
    }
}
int getlca(int u,int v){
    if(h[u] > h[v]) swap(u,v);
    for(int i = MLog;i>=0;i--){
        if(h[u] <= h[pa[i][v]]){
            v = pa[i][v];
        }
    }
    if(u==v) return u;
    for(int i = MLog;i>=0;i--){
        if(pa[i][u] != pa[i][v]){
            u = pa[i][u];
            v = pa[i][v];
        }
    }
    return pa[0][u];
}
void sub12(){
    for(int test = 1;test<=q;test++){
        int i,r;
        cin >> i >> r;
        int u = E[i].F, v = E[i].S;
        if(h[u] > h[v]) swap(u,v);
        if(st[v] <= st[r] && fn[r] <= fn[v]){
            ll ans = 1e17;
            for(int j = 1;j<=s;j++){
                if(st[v] <= st[c[j]]  && fn[c[j]] <= fn[v]){
                    ans = min(ans,d[r] + d[c[j]] - 2*d[getlca(r,c[j])]);
                }
            }
            if(ans == 1e17){
                cout << "oo" << '\n';
            }else{
                cout << ans << '\n';
            }
        }else{
            cout << "escaped" << '\n';
        }
    }
}
void sub3(){
    for(int test = 1;test<=q;test++){
        int i,r;
        cin >> i >> r;
        int u = E[i].F, v = E[i].S;
        if(h[u] > h[v]) swap(u,v);
        if(st[v] <= st[r] && fn[r] <= fn[v]){
            cout << 0 << '\n';
        }else{
            cout << "escaped" << '\n';
        }
    }
}
void solve() {
    cin >> n >> s >> q >> e;
    for(int i = 1; i<=n-1; i++) {
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
        E[i].F = u;
        E[i].S = v;
    }
    for(int i = 1; i<=s; i++) {
        cin >> c[i];
    }
    pre_dfs(e,0);
    build_lca();

    if(q*s<=5e7) {
        sub12();
        return;
    }
    if(s==n) {
        sub3();
        return;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    //freopen("inp.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    solve();
    return 0;
}

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