Submission #1130130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130130		Vedant18	Valley (BOI19_valley)	C++20	100 / 100	315 ms	56408 KiB

valley

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define in(a, b) for (ll i = (a); i <= (b); i++)                // in using i
#define inj(a, b) for (ll j = (a); j <= (b); j++)               // in using j
#define ink(a, b) for (ll k = (a); k <= (b); k++)               // in using k
#define inl(a, b) for (ll l = (a); l <= (b); l++)               // in using l
#define inr(a, b) for(ll i = (a); i >= (b); i--)                // in reverse
#define inrj(a, b) for(ll j = (a); j >= (b); j--)                // in reverse
#define inrk(a, b) for(ll k = (a); k >= (b); k--)                // in reverse
#define inrl(a, b) for(ll l = (a); l >= (b); l--)                // in reverse
#define tt ll tcs; cin>>tcs; while(tcs--)                       // include test cases
#define ina(arr,n) ll arr[(n+1)]={0}; in(1,n) cin>>arr[i]       // input arr of n elements
#define inv(vec,n) vector<ll> vec(n+1); vec[0]=0; in(1,n) cin>>vec[i]; // input vector of n elements
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pll pair <ll,ll>
#define vpll vector <pll>
#define sll set <ll>
#define vll vector<ll>
#define mll map <ll,ll>
#define all(x) x.begin(), x.end()
const ll mod=1e9+7;
#define vvll vector<vll>
#define pref(p,a,n) vll p(n+1); in(1,n) p[i]=p[i-1]+a[i];
#define vec2(a,n,m) vvll a(n+1,vll(m+1))
// #define vec2(a,n,m,val) vvll a(n+1,vll(m+1,val))

#define vec3(a,l,m,n) vector<vvll>a(l+1,vvll(m+1,vll(n+1)));
// #define vec3(a,l,m,n,val) vector<vvll>a(l+1,vvll(m+1,vll(n+1,val)));
# define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
struct edg{
    ll a,b,w;
    ll child;
};
int main(){
    FAST
    ll n,s,q,e;
    cin>>n>>s>>q>>e;
    vector<vector<pll>>adj(n+1);
    vector<edg>ee(n);
    for(ll i=1;i<n;i++){
        ll a,b,w;
        cin>>a>>b>>w;
        ee[i].a=a;
        ee[i].b=b;
        ee[i].w=w;
        adj[a].push_back({b,i});
        adj[b].push_back({a,i});
    }
    vll dpt(n+1);
    vll tin(n+1);
    vll tout(n+1);
    ll t=0;
    vll dis(n+1);
    vll closest(n+1,1e18);
    vector<bool> hashop(n+1);
    in(1,s){
        ll x;
        cin>>x;
        hashop[x]=1;
    }

    vector<vector<ll>>st(n+1,vll(log2(n)+1));
    vector<vector<ll>>ances(n+1,vll(log2(n)+1));

    //dis[x]-dis[v]+closest[v]
    function<void(ll,ll)> dfs=[&](ll v, ll p){
        t++;
        tin[v]=t;
        closest[v]=1e18;
        if(hashop[v]){
            closest[v]=0;
        }
        for(auto [x,id]:adj[v]){
            if(x!=p){
                dpt[x]=dpt[v]+1;
                dis[x]=dis[v]+ee[id].w;
                ee[id].child=x;
                dfs(x,v);
                closest[v]=min(closest[v],ee[id].w+closest[x]);
                ances[x][0]=v;
            }
        }
        tout[v]=t;
        // st[v][0]=min(closest[p]-dis[p],closest[v]-dis[v]);
    };
    //v[0] -->

    dfs(e,0);
    for(ll i=1;i<=n;i++){
        st[i][0]=closest[ances[i][0]]-dis[ances[i][0]];
    }
    auto is_anc=[&](ll v, ll p){
        return (tin[p]<=tin[v])&&(tout[p]>=tout[v]);
    };
    for(ll l=1;l<=log2(n);l++){
        for(ll i=1;i<=n;i++){
            ances[i][l]=ances[ances[i][l-1]][l-1];
            st[i][l]=min(st[i][l-1],st[ances[i][l-1]][l-1]);
        }
    }


    while(q--){
        ll i,r;
        cin>>i>>r;
        ll a=ee[i].child;
        if(is_anc(r,a)){
            ll gap=dpt[r]-dpt[a];
            ll x=r;
            ll mn=closest[r]-dis[r];
            for(ll j=log2(n);j>=0;j--){
                if(gap&(1<<j)){
                    mn=min(mn,st[x][j]);
                    x=ances[x][j];
                }
            }
            assert(x==a);
            ll ans=mn+dis[r];
            if(ans<=1e15){
                cout<<ans<<endl;
            }
            else{
                cout<<"oo"<<endl;
            }
        }
        else{
            cout<<"escaped\n";
        }
    }


}

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