Submission #639754

#	Time	Username	Problem	Language	Result	Execution time	Memory
639754		milisav	Valley (BOI19_valley)	C++14	100 / 100	212 ms	25308 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 ch[maxn];
long long md[maxn];
long long dd[maxn];
bool ex[maxn];
void dfs(int u,int pred=0) {
    if(ex[u]) md[u]=d[u];
    else md[u]=inf;
    for(auto eg:neigh[u]) {
        int v=eg.first;
        if(v!=pred) {
            d[v]=d[u]+eg.second;
            ch[v]=ch[u]+1;
            dfs(v,u);
            //cout<<u<<" "<<v<<" "<<" "<<eg.second<<endl;
            md[u]=min(md[u],md[v]);
        }
    }
    dd[u]=md[u]-2*d[u];
    //cout<<u<<" "<<md[u]<<" "<<dd[u]<<endl;
}
long long seg[4*maxn];
void add(int id,int l,int r,int p,long long v) {
    if(l==r) {
        seg[id]=v;
        return;
    }
    int m=(l+r)/2;
    if(p<=m) add(id*2+1,l,m,p,v);
    else add(id*2+2,m+1,r,p,v);
    seg[id]=min(seg[id*2+1],seg[id*2+2]);
}
long long query(int id,int l,int r,int x,int y) {
    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);
    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;
    add(0,0,n-1,ch[u],dd[u]);
    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];
            ans[id]=d[u]+query(0,0,n-1,ch[anc],ch[u]);
        }
    }
    for(auto eg:neigh[u]) {
        int v=eg.first;
        int w=eg.second;
        if(v!=pred) {
            dfs_ans(v,u);
        }
    }
    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});
    }
    for(int i=1;i<=s;i++) {
        int p;
        scanf("%d",&p);
        ex[p]=true;
    }
    dfs(e);
    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 'void dfs_ans(int, int)':
valley.cpp:70:13: warning: unused variable 'w' [-Wunused-variable]
   70 |         int w=eg.second;
      |             ^
valley.cpp: In function 'int main()':
valley.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d %d %d %d",&n,&s,&q,&e);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%d %d %d",&u,&v,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
valley.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         scanf("%d",&p);
      |         ~~~~~^~~~~~~~~
valley.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         scanf("%d %d",&r,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

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