Submission #638613

#	Time	Username	Problem	Language	Result	Execution time	Memory
638613		milisav	Valley (BOI19_valley)	C++14	100 / 100	415 ms	27392 KiB

valley

#include<bits/stdc++.h>
#define maxn 100005
#define inf 1000000000000000000ll
#define pinf 10000000000000000ll
using namespace std;
int n,s,q,e;
vector<pair<int,int> > neigh[maxn];
long long d[maxn];
int ord[maxn];
int l[maxn];
int r[maxn];
int t=1;
void dfs(int u,int pred=0) {
    l[u]=r[u]=t;
    ord[t]=u;
    t++;
    for(auto eg:neigh[u]) {
        int v=eg.first;
        if(v!=pred) {
            d[v]=d[u]+eg.second;
            dfs(v,u);
            r[u]=r[v];
        }
    }
}
long long seg[4*maxn];
long long laz[4*maxn];
bool ex[maxn];
inline void propagate(int id,int l,int r) {
    seg[id]+=laz[id];
    if(l!=r) {
        laz[id*2+1]+=laz[id];
        laz[id*2+2]+=laz[id];
    }
    laz[id]=0;
}
void create_seg(int id,int l,int r) {
    if(l==r) {
        if(ex[ord[l]]) seg[id]=d[ord[l]];
        else seg[id]=inf;
        return;
    }
    int m=(l+r)/2;
    create_seg(id*2+1,l,m);
    create_seg(id*2+2,m+1,r);
    seg[id]=min(seg[id*2+1],seg[id*2+2]);
    //cout<<id<<" "<<l<<" "<<r<<" "<<seg[id]<<endl;
}
void add(int id,int l,int r,int x,int y,int off) {
    propagate(id,l,r);
    if(y<l || r<x) return;
    if(x<=l && r<=y) {
        laz[id]+=off;
        propagate(id,l,r);
        return;
    }
    int m=(l+r)/2;
    add(id*2+1,l,m,x,y,off);
    add(id*2+2,m+1,r,x,y,off);
    seg[id]=min(seg[id*2+1],seg[id*2+2]);
}
long long query(int id,int l,int r,int x,int y) {
    propagate(id,l,r);
    if(y<l || r<x) return inf;
    if(x<=l && r<=y) return seg[id];
    int m=(l+r)/2;
    long long v1=query(id*2+1,l,m,x,y);
    long long v2=query(id*2+2,m+1,r,x,y);
    seg[id]=min(seg[id*2+1],seg[id*2+2]);
    return min(v1,v2);
}
int ux[maxn];
int vx[maxn];
long long ans[maxn];
vector<pair<int,int> > queries[maxn];
bool ins[maxn];
void dfs_ans(int u,int pred=0) {
    ins[u]=true;
    for(auto que:queries[u]) {
        int road=que.first;
        int id=que.second;
        if(!ins[ux[road]] || !ins[vx[road]]) {
            ans[id]=-1;
        }
        else {
            int anc=ux[road];
            if(d[vx[road]]>d[ux[road]]) anc=vx[road];
            //cout<<id<<" "<<anc<<" "<<l[anc]<<" "<<r[anc]<<endl;
            ans[id]=query(0,1,n,l[anc],r[anc]);
        }
    }
    for(auto eg:neigh[u]) {
        int v=eg.first;
        int w=eg.second;
        if(v!=pred) {
            //cout<<u<<" "<<v<<" "<<l[v]<<" "<<r[v]<<" "<<w<<endl;
            add(0,1,n,1,l[v]-1,w);
            add(0,1,n,l[v],r[v],-w);
            add(0,1,n,r[v]+1,n,w);
            dfs_ans(v,u);
            add(0,1,n,1,l[v]-1,-w);
            add(0,1,n,l[v],r[v],w);
            add(0,1,n,r[v]+1,n,-w);
        }
    }
    ins[u]=false;

}
int main() {
    scanf("%d %d %d %d",&n,&s,&q,&e);
    for(int i=1;i<=n-1;i++) {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        ux[i]=u;
        vx[i]=v;
        neigh[u].push_back({v,w});
        neigh[v].push_back({u,w});
    }
    dfs(e);
    for(int i=1;i<=s;i++) {
        int p;
        scanf("%d",&p);
        ex[p]=true;
    }
    create_seg(0,1,n);
    for(int i=1;i<=q;i++) {
        int r,v;
        scanf("%d %d",&r,&v);
        queries[v].push_back({r,i});
    }
    dfs_ans(e);
    for(int i=1;i<=q;i++) {
        if(ans[i]==-1) printf("escaped\n");
        else {
            if(ans[i]<pinf) printf("%lld\n",ans[i]);
            else printf("oo\n");
        }
    }
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     scanf("%d %d %d %d",&n,&s,&q,&e);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         scanf("%d %d %d",&u,&v,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
valley.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf("%d",&p);
      |         ~~~~~^~~~~~~~~
valley.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         scanf("%d %d",&r,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

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