Submission #139852

#	Time	Username	Problem	Language	Result	Execution time	Memory
139852		ae04071	Valley (BOI19_valley)	C++11	100 / 100	400 ms	22704 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using lli = long long;

const lli INF = 1e17;
struct seg_tr{
    const static int MAX = 1<<17;
    lli tr[MAX<<1];
    void init() {
        for(int i=0;i<MAX+MAX;i++) tr[i] = INF;
    }
    void upd(int cur,lli val) {
        cur+=MAX;
        tr[cur] = val;
        cur>>=1;
        while(cur) {
            int nx=cur<<1;
            tr[cur] = min(tr[nx],tr[nx+1]);
            cur>>=1;
        }
    }
    lli get(int l,int r) {
        lli ret = INF;
        l+=MAX; r+=MAX;
        while(l<=r) {
            ret = min({ret, tr[l],tr[r]});
            if(l&1) l++;
            if(!(r&1)) r--;
            l>>=1; r>>=1;
        }
        return ret;
    }
}st;

lli mx[100001];
int dfn[100001],out[100001],dn=0,n,m,q,r,chk[100001];
vector<pair<int,int>> adj[100001];

lli ans[100001];
int de[100001];
vector<pair<int,int>> qa[100001];
void dfs(int cur,int p) {
    dfn[cur]=++dn;
    mx[cur] = INF;
    for(auto &it:adj[cur]) if(it.second!=p) {
        dfs(it.second,cur);
        mx[cur] = min(mx[cur], mx[it.second]+it.first);
    }
    if(chk[cur]) mx[cur] = 0;
    out[cur] = dn;
}
void dfs2(int cur,int p,int d,lli w) {
    st.upd(d, mx[cur]-w);
    de[cur]=d;
    for(auto &it:qa[cur]){
        ans[it.second] = st.get(de[it.first], d) + w;
    }
    for(auto &it:adj[cur]) if(it.second != p) {
        dfs2(it.second,cur,d+1,w+it.first);
    }
    st.upd(d, INF);
}

struct edge{
    int u,v,w;
}ea[100001];

int main() {
    scanf("%d%d%d%d",&n,&m,&q,&r);
    for(int i=1;i<n;i++) {
        scanf("%d%d%d",&ea[i].u,&ea[i].v,&ea[i].w);
        adj[ea[i].u].push_back({ea[i].w,ea[i].v});
        adj[ea[i].v].push_back({ea[i].w,ea[i].u});
    }
    for(int i=0;i<m;i++) {
        int v;
        scanf("%d",&v);
        chk[v]=1;
    }
    dfs(r,0);
    
    for(int i=0;i<q;i++) {
        int a,b,u,v;
        scanf("%d%d",&a,&b);
        u = ea[a].u,v=ea[a].v;
        if(dfn[u]>dfn[v]) swap(u,v);
        
        if(dfn[b]<dfn[v] || dfn[b] > out[v]) ans[i] = -1;
        else qa[b].push_back({v,i});
    }
    dfs2(r,0,0,0);
    
    for(int i=0;i<q;i++) {
        if(ans[i]==-1) puts("escaped");
        else if(ans[i]>=INF/10) puts("oo");
        else printf("%lld\n",ans[i]);
    }
    
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d",&n,&m,&q,&r);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&ea[i].u,&ea[i].v,&ea[i].w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&v);
         ~~~~~^~~~~~~~~
valley.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

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