Submission #1085790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085790		DucNguyen2007	Valley (BOI19_valley)	C++14	100 / 100	170 ms	36568 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=1e5+5;
const ll inf=2e18;
int n,q,m,e,b[maxN+1],st[maxN+1],en[maxN+1],timer=0,tour[maxN+1],lef[maxN+1],righ[maxN+1];
struct canh
{
    int u,v;
    ll w;
}a[maxN+1];
vector<pii> adj[maxN+1],vec[maxN+1];
struct query
{
    int pos,u;
}p[maxN+1];
ll ans[maxN+1],h[maxN+1];
void pre_dfs(int u,int p)
{
    tour[++timer]=u;
    st[u]=timer;
    for(auto [v,w]:adj[u])
    {
        if(v!=p)
        {
            h[v]=h[u]+w;
            pre_dfs(v,u);
        }
    }
    en[u]=timer;
}
struct segment
{
    struct Node
    {
        ll s,lazy;
        Node()
        {
            s=inf;
            lazy=0;
        }
        Node(ll S,ll laz)
        {
            s=S;
            lazy=laz;
        }
    }sum[4*maxN+1];
    Node meg(Node x,Node y)
    {
        Node res;
        res.s=min(x.s,y.s);
        res.lazy=0;
        return res;
    }
    int l,r;
    ll val;
    void lazyupdate(int x,int low,int high)
    {
        if(low==high)
        {
            return;
        }
        sum[2*x].s+=sum[x].lazy;
        sum[2*x].lazy+=sum[x].lazy;
        sum[2*x+1].s+=sum[x].lazy;
        sum[2*x+1].lazy+=sum[x].lazy;
        sum[x].lazy=0;
    }
    void Build(int x,int low,int high)
    {
        if(low==high)
        {
            sum[x]=Node(h[tour[b[low]]],0);
            return;
        }
        int mid=(low+high)/2;
        Build(2*x,low,mid);
        Build(2*x+1,mid+1,high);
        sum[x]=meg(sum[2*x],sum[2*x+1]);
    }
    void Update(int x,int low,int high)
    {
        if(low>r||high<l)
        {
            return;
        }
        if(low>=l&&high<=r)
        {
            sum[x].s+=val;
            sum[x].lazy+=val;
            return;
        }
        lazyupdate(x,low,high);
        int mid=(low+high)/2;
        Update(2*x,low,mid);
        Update(2*x+1,mid+1,high);
        sum[x]=meg(sum[2*x],sum[2*x+1]);
    }
    void update_val(int l,int r,ll val)
    {
        this->l=l;
        this->r=r;
        this->val=val;
        Update(1,1,m);
    }
    Node get(int x,int low,int high)
    {
        if(low>r||high<l)
        {
            return Node(inf,0);
        }
        if(low>=l&&high<=r)
        {
            return sum[x];
        }
        lazyupdate(x,low,high);
        int mid=(low+high)/2;
        Node get1=get(2*x,low,mid);
        Node get2=get(2*x+1,mid+1,high);
        return meg(get1,get2);
    }
    ll query(int l,int r)
    {
        this->l=l;
        this->r=r;
        if(l>r)
        {
            return inf;
        }
        else return get(1,1,m).s;
    }
}str;
bool check(int u,int v)
{
    return (st[u]<=st[v]&&st[v]<=en[u]);
}
void dfs(int u,int p)
{
    for(auto [j,id]:vec[u])
    {
        if(check(j,u))
        {
            ans[id]=min(ans[id],str.query(lef[j],righ[j]));
        }
        else ans[id]=min(ans[id],min(str.query(1,lef[j]-1),str.query(righ[j]+1,m)));
        //cout<<u<<" "<<j<<" "<<id<<" "<<check(j,u)<<" "<<lef[j]<<" "<<righ[j]<<'\n';
    }
    for(auto [v,w]:adj[u])
    {
        if(v==p)
        {
            continue;
        }
        str.update_val(1,m,w);
        str.update_val(lef[v],righ[v],-2*w);
        //cout<<u<<" "<<v<<" "<<w<<" "<<str.query(2,2)<<'\n';
        dfs(v,u);
        str.update_val(1,m,-w);
        str.update_val(lef[v],righ[v],2*w);
    }
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>q>>e;
    for(int i=1;i<n;i++)
    {
        cin>>a[i].u>>a[i].v>>a[i].w;
        adj[a[i].u].push_back({a[i].v,a[i].w});
        adj[a[i].v].push_back({a[i].u,a[i].w});
    }
    pre_dfs(1,0);
    for(int i=1;i<=m;i++)
    {
        int u;
        cin>>u;
        b[i]=st[u];
    }
    for(int i=1;i<=q;i++)
    {
        cin>>p[i].pos>>p[i].u;
        int tmp;
        if(st[a[p[i].pos].u]>st[a[p[i].pos].v])
        {
            tmp=a[p[i].pos].u;
        }
        else tmp=a[p[i].pos].v;
        if((check(tmp,p[i].u)&&check(tmp,e))||(!check(tmp,p[i].u)&&!check(tmp,e)))
        {
            ans[i]=-1;
        }
        else
        {
            ans[i]=inf;
            vec[p[i].u].push_back({tmp,i});
        }
    }
    sort(b+1,b+m+1);
    for(int i=1;i<=n;i++)
    {
        lef[i]=lower_bound(b+1,b+m+1,st[i])-b;
        righ[i]=upper_bound(b+1,b+m+1,en[i])-b-1;
    }
    str.Build(1,1,m);
    /*str.update_val(1,m,3);
    cout<<str.query(2,2)<<'\n';*/
    dfs(1,0);
    for(int i=1;i<=q;i++)
    {
        if(ans[i]==-1)
        {
            cout<<"escaped";
        }
        else if(ans[i]==inf)
        {
            cout<<"oo";
        }
        else cout<<ans[i];
        cout<<'\n';
    }
}

Compilation message (stderr)

valley.cpp: In function 'void pre_dfs(int, int)':
valley.cpp:27:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for(auto [v,w]:adj[u])
      |              ^
valley.cpp: In function 'void dfs(int, int)':
valley.cpp:144:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  144 |     for(auto [j,id]:vec[u])
      |              ^
valley.cpp:153:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |     for(auto [v,w]:adj[u])
      |              ^

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