Submission #964484

#	Time	Username	Problem	Language	Result	Execution time	Memory
964484		irmuun	Valley (BOI19_valley)	C++17	100 / 100	173 ms	36916 KiB

valley

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll N=1e5+5;

ll n,s,q,e;
vector<array<ll,3>>adj[N];
vector<pair<ll,ll>>edge;
vector<bool>shop(N,0),path(N,0);
vector<ll>cnt(N,0),d(N,1e18),depth(N),par(N);
ll cur=0;
vector<pair<ll,ll>>que[N];
vector<ll>ans(N,0);

void dfs(ll x,ll p){
    par[x]=p;
    cnt[x]=0;
    if(shop[x]){
        d[x]=0;
        cnt[x]=1;
    }
    for(auto [y,w,i]:adj[x]){
        if(y!=p){
            depth[y]=depth[x]+1;
            dfs(y,x);
            cnt[x]+=cnt[y];
            d[x]=min(d[x],d[y]+w);
        }
    }
};

struct segtree{
    ll n;
    vector<ll>d;
    void set(ll sz){
        n=sz;
        d.resize(4*n);
        build(1,1,n);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]=1e18;
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=min(d[node*2],d[node*2+1]);
    }
    ll query(ll node,ll l,ll r,ll L,ll R){
        if(l > R || r < L || L > R){
            return 1e18;
        }
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return min(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
    }
    void update(ll node,ll l,ll r,ll k,ll val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,k,val);
        update(node*2+1,mid+1,r,k,val);
        d[node]=min(d[node*2],d[node*2+1]);
    }
}sg;

void run(ll x,ll p){
    if(d[x]==1e18) sg.update(1,1,N,depth[x],1e18);
    else sg.update(1,1,N,depth[x],d[x]-cur);
    for(auto [I,ind]:que[x]){
        if(path[I]==false){
            ans[ind]=-1;
            continue;
        }
        ll low=edge[I-1].ff;
        if(par[low]!=edge[I-1].ss){
            low=edge[I-1].ss;
        }
        ll D=sg.query(1,1,N,depth[low],depth[x]);
        if(D==1e18){
            ans[ind]=-2;
        }
        else{
            ans[ind]=D+cur;
        }
    }
    for(auto [y,w,j]:adj[x]){
        if(y!=p){
            path[j]=true;
            cur+=w;
            run(y,x);
            path[j]=false;
            cur-=w;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>s>>q>>e;
    for(ll i=1;i<n;i++){//edge
        ll a,b,w;
        cin>>a>>b>>w;
        edge.pb({a,b});
        adj[a].pb({b,w,i});
        adj[b].pb({a,w,i});
    }
    for(ll i=1;i<=s;i++){//shop
        ll c;
        cin>>c;
        shop[c]=true;
    }
    depth[e]=1;
    dfs(e,0);
    sg.set(N);
    for(ll i=1;i<=q;i++){
        ll I,r;
        cin>>I>>r;
        que[r].pb({I,i});
    }
    run(e,0);
    for(ll i=1;i<=q;i++){
        if(ans[i]==-1){
            cout<<"escaped\n";
        }
        else if(ans[i]==-2){
            cout<<"oo\n";
        }
        else{
            cout<<ans[i]<<"\n";
        }
    }
}

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