Submission #380907

#	Time	Username	Problem	Language	Result	Execution time	Memory
380907		leaked	Valley (BOI19_valley)	C++14	100 / 100	500 ms	36576 KiB

valley

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx,avx2,tune=native")
#define m_p make_pair
#define f first
#define s second
#define vec vector
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pw(x) (1LL<<x)
#define pb push_back
#define sz(x) (int)x.size()
#define endl '\n'
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define print(x) cerr<<"[ "<<(#x)<<": "<<x<<" ]"<<endl;cout.flush();
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template<class T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T> bool umin(T &a,const T b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T b){return (a<b?a=b,1:0);}
const int N=1e5+1;
const ll inf=1e17;
int up[N][20];
int in[N],out[N],e,n,m,q,tt=-1;
bool painted[N];
vec<pii>edges;
ll p[4*N];
ll t[4*N];
vec<pii>g[N];
ll ans[N];
vec<array<int,3>>qry[N];
void push(int v,int tl,int tr){
    if(tl==tr || !p[v]){
        return;
    }
    p[2*v]+=p[v];
    p[2*v+1]+=p[v];
    t[2*v]+=p[v];
    t[2*v+1]+=p[v];
    p[v]=0;
}
void upd(int l,int r,ll x,int v,int tl,int tr){
    if(tl>=l && tr<=r){
        p[v]+=x;
        t[v]+=x;
        return;
    }
    if(tl>r || tr<l) return;
    int tm=(tl+tr)>>1;
    push(v,tl,tr);
    upd(l,r,x,2*v,tl,tm);
    upd(l,r,x,2*v+1,tm+1,tr);
    t[v]=min(t[2*v],t[2*v+1]);
}
void dfs1(int v,ll d,int p){
    in[v]=++tt;
    if(painted[v]){
        upd(in[v],in[v],-inf,1,0,n-1);
        upd(in[v],in[v],d,1,0,n-1);
    }
    up[v][0]=p;
    for(int i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1];
    for(auto &z : g[v]){
        if(z.f==p) continue;
        dfs1(z.f,d+z.s,v);
    }
    out[v]=tt;
}
bool is(int a,int b){
    return in[a]<=in[b]&&out[a]>=out[b];
}
int lca(int a,int b){
    if(is(a,b)) return a;
    if(is(b,a)) return b;
    for(int i=19;i>=0;i--){
        if(!is(up[a][i],b)) a=up[a][i];
    }
    return up[a][0];
}
void dfs2(int v,int p){
    int lc=lca(v,e);
    for(auto &z : qry[v]){
        int a=z[1],b=z[2];
        int i=z[0];
        if(is(b,a)) swap(a,b);
//        print(is(lc,a));print(z[0]);print(z[1]);print(z[2]);
        if((is(lc,a) && is(b,v)) || (is(lc,a) && is(b,e))){
            if(is(b,v)){
                upd(0,n-1,inf,1,0,n-1);
                upd(in[b],out[b],-inf,1,0,n-1);
                ans[i]=t[1];
                upd(0,n-1,-inf,1,0,n-1);
                upd(in[b],out[b],inf,1,0,n-1);
            }
            else{
                upd(in[b],out[b],inf,1,0,n-1);
                ans[i]=t[1];
                upd(in[b],out[b],-inf,1,0,n-1);
            }
        }
        else{
            ans[i]=-inf;
        }
    }
    for(auto &z : g[v]){
        if(z.f==p) continue;
        upd(0,n-1,z.s,1,0,n-1);
        upd(in[z.f],out[z.f],-2*z.s,1,0,n-1);
        dfs2(z.f,v);
        upd(0,n-1,-z.s,1,0,n-1);
        upd(in[z.f],out[z.f],2*z.s,1,0,n-1);
    }
}
signed main(){
    fast_ioi;
    cin>>n>>m>>q>>e;
    --e;
    for(int i=1;i<n;i++){
        int v,u,w;
        cin>>v>>u>>w;--v;--u;
        g[v].pb({u,w});
        g[u].pb({v,w});
        edges.pb({v,u});
    }
    upd(0,n-1,inf,1,0,n-1);
    for(int i=0;i<m;i++){
        int x;
        cin>>x;--x;
        painted[x]=1;
    }
    for(int i=0;i<q;i++){
        int a,b;
        cin>>a>>b;--a;--b;
        qry[b].pb({i,edges[a].f,edges[a].s});
//        print(edges[a].f);
//        print(edges[a].s);
//        print(b);
    }
    dfs1(0,0,0);
    dfs2(0,0);
    for(int i=0;i<q;i++){
        if(ans[i]>=inf/10*9){
            cout<<"oo";
        }
        else if(ans[i]==-inf){
            cout<<"escaped";
        }
        else{
            cout<<ans[i];
        }
        cout<<endl;
    }
    return 0;
}
/*
5 2 1 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
4 5

*/

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