Submission #866790

#	Time	Username	Problem	Language	Result	Execution time	Memory
866790		Eliorita	Valley (BOI19_valley)	C++14	100 / 100	303 ms	61432 KiB

valley

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define x first
#define y second
#define getbit(u,i) ((u>>i)&1)
#define all(x) x.begin(),x.end()
#define N 200001
using namespace std;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
struct node
{
    int val,lazy;
} tree[4*N];
int n,s,e,q,a[N],num[N],tail[N],h[N],p[N][18],cnt,rev[N],d[N],ans[N];
vector<ii> g[N],Q[N];
ii ed[N];
void down(int id,int l,int r)
{
    tree[id].val+=tree[id].lazy;
    if(l!=r)
    {
        tree[id*2].lazy+=tree[id].lazy;
        tree[id*2+1].lazy+=tree[id].lazy;
    }
    tree[id].lazy=0;
}
void update(int id,int l,int r,int u,int v,int val)
{
    down(id,l,r);
    if(l>v||r<u||l>r||u>v) return;
    if(l>=u&&r<=v)
    {
        tree[id].val+=val;
        if(l!=r)
        {
            tree[id*2].lazy+=val;
            tree[id*2+1].lazy+=val;
        }
        return;
    }
    int m=(l+r)/2;
    update(id*2,l,m,u,v,val);
    update(id*2+1,m+1,r,u,v,val);
    tree[id].val=min(tree[id*2].val,tree[id*2+1].val);
}
int get(int id,int l,int r,int u,int v)
{
    down(id,l,r);
    if(l>v||r<u||l>r||u>v) return LLONG_MAX;
    if(l>=u&&r<=v) return tree[id].val;
    int m=(l+r)/2;
    return min(get(id*2,l,m,u,v),get(id*2+1,m+1,r,u,v));
}
void dfs(int u,int pre)
{
    num[u]=++cnt;
    rev[cnt]=u;
    h[u]=h[pre]+1;
    p[u][0]=pre;
    for(int i=1;i<=17;i++) p[u][i]=p[p[u][i-1]][i-1];
    for(ii v : g[u])
    {
        if(v.x==pre) continue;
        d[v.x]=d[u]+v.y;
        dfs(v.x,u);
    }
    tail[u]=cnt;
}
int lca(int u,int v)
{
    if(h[u]<h[v]) swap(u,v);
    for(int i=17;i>=0;i--)
    {
        if(h[p[u][i]]>=h[v]) u=p[u][i];
    }
    if(u==v) return u;
    for(int i=17;i>=0;i--)
    {
        if(p[u][i]!=p[v][i])
        {
            u=p[u][i];
            v=p[v][i];
        }
    }
    return p[u][0];
}
void reroot(int u,int pre)
{
//    cout<<u<<'\n';
//    for(int i=1;i<=s;i++) cout<<get(1,1,s,i,i)<<' ';
//    cout<<'\n';
    for(ii c : Q[u])
    {
        int cur=ed[c.x].x;
//        if(u==5)cout<<cur<<' ';
        if(lca(u,cur)!=cur) ans[c.y]=-1;
        else
        {
            int l=lower_bound(a+1,a+s+1,num[cur])-a;
            int r=upper_bound(a+1,a+s+1,tail[cur])-a-1;
            if(l>r) ans[c.y]=-2;
            else ans[c.y]=get(1,1,s,l,r);
        }
    }
    for(ii v : g[u])
    {
        if(v.x==pre) continue;
        int l=lower_bound(a+1,a+s+1,num[v.x])-a;
        int r=upper_bound(a+1,a+s+1,tail[v.x])-a-1;
//        if(v.x==3)  cout<<num[3]<<' '<<l<<' '<<r<<'\n';
        update(1,1,s,1,s,v.y);
        update(1,1,s,l,r,-2*v.y);
        reroot(v.x,u);
        update(1,1,s,1,s,-v.y);
        update(1,1,s,l,r,2*v.y);
    }
}
signed main()
{
    if(fopen("demo.inp","r"))
    {
        freopen("demo.inp","r",stdin);
        freopen("demo.out","w",stdout);
    }
    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;
        ed[i]={u,v};
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    dfs(e,0);
    for(int i=1;i<n;i++)
    {
        if(h[ed[i].x]<h[ed[i].y]) swap(ed[i].y,ed[i].x);
    }
    for(int i=1;i<=s;i++) {cin>>a[i]; a[i]=num[a[i]];}
//    cout<<upper_bound(a+1,a+s+1,3)-a-1;
//    return 0;
    sort(a+1,a+s+1);
    for(int i=1;i<=s;i++) update(1,1,s,i,i,d[rev[a[i]]]);
    for(int i=1;i<=q;i++)
    {
        int k,r;
        cin>>k>>r;
        Q[r].pb({k,i});
    }
    reroot(e,0);
    for(int 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';
    }
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen("demo.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen("demo.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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