Submission #1258147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258147		future	Valley (BOI19_valley)	C++20	100 / 100	265 ms	25300 KiB

valley

#include <bits/stdc++.h>

using namespace std;
int n,q,s,e;
vector<array<int,3>>g[100005];
int db[100005];
long long dis[100005];
int start[100005];
int stop[100005];
int tp[100005];
int timee;
long long tree[400005],lazy[400005];
int pos[100005];
void init(int id,int l,int r) {
    if(l==r) {
        tree[id]=dis[tp[l]];
        return ;
    }
    int mid=(l+r)/2;
    init(id*2,l,mid);
    init(id*2+1,mid+1,r);
    tree[id]=min(tree[id*2],tree[id*2+1]);
}
void push(int id) {
    if(lazy[id]==0)return;
    tree[id*2]+=lazy[id];
    tree[id*2+1]+=lazy[id];
    lazy[id*2]+=lazy[id];
    lazy[id*2+1]+=lazy[id];
    lazy[id]=0;
}
void upd(int id,int l,int r,int u,int v,int val) {
    if(l>v||r<u)return;
    if(l>=u&&r<=v) {
        tree[id]+=val;
        lazy[id]+=val;
        return;
    }
    push(id);
    int mid=(l+r)/2;
    upd(id*2,l,mid,u,v,val);
    upd(id*2+1,mid+1,r,u,v,val);
    tree[id]=min(tree[id*2],tree[id*2+1]);
}
long long getmin(int id,int l,int r,int u,int v) {
    if(l>v||r<u)return 1e18;
    if(l>=u&&r<=v)return tree[id];
    push(id);
    int mid=(l+r)/2;
    return min(getmin(id*2,l,mid,u,v),getmin(id*2+1,mid+1,r,u,v));
}
void dfs(int u,int pa) {
    timee++;
    start[u]=timee;
    tp[timee]=u;
    for(auto [v,w,id]:g[u])if(v!=pa) {
            dis[v]=dis[u]+w;
            pos[id]=v;
            dfs(v,u);
        }
    stop[u]=timee;
}
long long ans[100005];
vector<array<int,2>>vec[100005];
void dfs_query(int u,int pa) {
    for(auto [i,id]:vec[u]) {
        int l=start[pos[i]];
        int r=stop[pos[i]];
        if(start[u]>=l&&start[u]<=r)ans[id]=getmin(1,1,n,l,r);
        else ans[id]=min(getmin(1,1,n,1,l-1),getmin(1,1,n,r+1,n));
    }
    for(auto[v,w,_]:g[u])if(v!=pa) {
            upd(1,1,n,1,start[v]-1,+w);
            upd(1,1,n,stop[v]+1,n,+w);
            upd(1,1,n,start[v],stop[v],-w);
            dfs_query(v,u);
            upd(1,1,n,1,start[v]-1,-w);
            upd(1,1,n,stop[v]+1,n,-w);
            upd(1,1,n,start[v],stop[v],+w);
        }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>s>>q>>e;
    for(int i=1; i<n; i++) {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w,i});
        g[v].push_back({u,w,i});
    }
    while(s--) {
        int u;
        cin>>u;
        db[u]=1;
    }
    dfs(1,0);
    for(int i=1; i<=n; i++)if(db[i]==0)dis[i]=1e18;
    dis[e]=-1e18;
    init(1,1,n);
    for(int i=1; i<=q; i++) {
        int I,r;
        cin>>I>>r;
        vec[r].push_back({I,i});
    }
    dfs_query(1,0);
    for(int i=1; i<=q; i++) {
        if(ans[i]<0) {
            cout<<"escaped"<<'\n';
            continue;
        }
        if(ans[i]>1e17)cout<<"oo"<<'\n';
        else cout<<ans[i]<<'\n';
    }
    return 0;
}

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