Submission #876358

#	Time	Username	Problem	Language	Result	Execution time	Memory
876358		imarn	Valley (BOI19_valley)	C++14	23 / 100	666 ms	138144 KiB

valley

#include<bits/stdc++.h>
#define ld long double
#define pii pair<int,ll>
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define f first
#define s second
#define vi vector<int>
#define vll vector<long long>
#define vpii vector<pii>
#define ll long long
using namespace std;
const int N=1e5+5;
vector<pii>g[N],an[N];pii ro[N];
int dep[N]{0},node[N]{0};
int tin[N]{0},tout[N]{0};
int sz[N]{0};bool vis[N]{0};
int t=0;
void dfs(int u,int p,int l){
    dep[u]=l;tin[u]=++t;
    for(auto v:g[u]){
        if(v.f==p)continue;
        dfs(v.f,u,l+1);
    }tout[u]=t;
}
int getsz(int u,int p){
    sz[u]=1;
    for(auto v:g[u]){
        if(v.f==p||vis[v.f])continue;
        sz[u]+=getsz(v.f,u);
    }return sz[u];
}
int getct(int u,int p,int re){
    for(auto v:g[u]){
        if(v.f==p||vis[v.f])continue;
        if(sz[v.f]*2>re)return getct(v.f,u,re);
    }return u;
}
void getdist(int u,int p,int x,ll cur){
    for(auto v:g[u]){
        if(vis[v.f]||v.f==p)continue;
        getdist(v.f,u,x,cur+v.s);
    }an[u].pb({x,cur});
}
void play(int u){
    int x=getct(u,u,getsz(u,u));
    vis[x]=1;
    getdist(x,x,x,0);
    for(auto v:g[x]){
        if(vis[v.f])continue;
        play(v.f);
    }
}
struct segment{
    vector<pii>v;
    vector<ll>t,k;
    void build(){
        int n=sz(v);
        t.resize(2*n);
        for(int i=0;i<n;i++)t[i+n]=v[i].s,k.pb(v[i].f);
        for(int i=n-1;i>=1;i--)t[i]=min(t[2*i],t[2*i+1]);
    }
    int qr(int l,int r,ll res=1e18){
        if(t.size()==0)return res;
        l = lower_bound(k.begin(),k.end(),l)-k.begin();
        r = upper_bound(k.begin(),k.end(),r)-k.begin();
        for(l+=sz(v),r+=sz(v);l<r;l>>=1,r>>=1){
            if(l&1)res=min(res,t[l++]);
            if(r&1)res=min(res,t[--r]);
        }return res;
    }
}seg[N];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,s,q,e;cin>>n>>s>>q>>e;
    for(int i=1,u,v,w;i<n;i++)cin>>u>>v>>w,g[u].pb({v,w}),g[v].pb({u,w}),ro[i]={u,v};
    dfs(e,e,0);play(e);
    for(int i=1,u;i<=s;i++)cin>>u,node[u]=1;
    for(int i=1;i<=n;i++){
        if(!node[i])continue;
        for(auto it : an[i])seg[it.f].v.pb({tin[i],it.s});
    }
    for(int i=1;i<=n;i++)sort(all(seg[i].v)),seg[i].build();
    while(q--){
        int i,r,x,y;ll ans=1e18;cin>>i>>r;
        tie(x,y)=ro[i];if(dep[x]<dep[y])swap(x,y);
        if(!(tin[x]<=tin[r]&&tout[r]<=tout[x])){cout<<"escaped\n";continue;}
        for(auto it : an[r])ans=min(ans,it.s+seg[it.f].qr(tin[x],tout[x]));
        if(ans==1e18)cout<<"oo\n";else cout<<ans<<"\n";
    }
}

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