Submission #1110328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110328		0pt1mus23	Valley (BOI19_valley)	C++14	0 / 100	57 ms	79528 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
int nxt(){ int x;cin>>x; return x; }
const int mod = 1e9 +7, sze = 1e5 +10, inf = INT_MAX, LG = 20;

pair<int,int> edge[sze];
int sp[sze];
vector<pair<int,int>> graph[sze];
int timer =0; 
int gir[sze];
int cix[sze];
int up[LG][sze];
int dp[LG][sze];
int as[sze];
int dist[sze];
int depth[sze];

void dfs(int node,int par=0){
    if(sp[node]){
        as[node]=0;
    }
    gir[node]=++timer;
    up[0][node]=par;
    for(int i =1;i<LG;i++){
        up[i][node]=up[i-1][up[i-1][node]];
    }

    for(auto [v,w]:graph[node]){
        if(v!=par){
            depth[v]=depth[node]+1;
            dist[v]=dist[node] + w;
            dfs(v,node);
            as[node]=min(as[node],as[v] + w);
        }
    }
    cix[node]=++timer;
}
void dps(int node,int par=0){
    
    if(as[node]!=inf){
        dp[0][node]= -dist[node] + as[node];
    }

    if(as[ up[0][node] ]!=inf){
        dp[0][node]= min(dp[0][node], -dist[ up[0][node] ] + as[ up[0][node] ]);
    }
    for(int i =1;i<LG;i++){
        dp[i][node]=min(dp[i-1][node], dp[i-1][ up[i-1][node] ]);
    }
    for(auto [v,w]:graph[node]){
        if(v!=par){
            dps(v,node);
        }
    }
}

int in(int u,int v){
    return (gir[v]<=gir[u] && cix[v]>=cix[u]);
}

int lca(int u,int v){
    if(in(u,v)){
        return v;
    }
    if(in(v,u)){
        return u;
    }

    for(int i = LG-1;i>=0;i--){
        if(!in( up[i][u],v )){
            u = up[i][u];
        }
    }
    return up[0][u];
}

int qry(int u,int v){
    int res=inf;

    if(as[u]!=inf){
        res=as[u] - dist[u];
    }
    for(int i =LG-1;i>=0;i--){
        if(depth[u] - (1<<i) >= depth[v]){
            res=min(res, dp[i][u]);
            u = up[i][u];
        }
    }


    return res;
}

void fast(){
    int n,s,q,root,x;
    cin>>n>>s>>q>>root;
    for(int i=0;i<=n;i++){
        as[i]=inf;
        dp[i][0]=inf;
    }

    for(int i =1;i<=n-1;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edge[i]={u,v};
        graph[u].pb({v,w});
        graph[v].pb({u,w});
    }
    for(int i=1;i<=s;i++){
        cin>>x;
        sp[x]=1;
    }
    
    dfs(root);
    dps(root);

    while(q--){
        int idx, u ;
        cin>>idx>>u;
        auto[ k,v ] = edge[idx];
        if(depth[k]<depth[v]){
            swap(k,v);
        }
        if(lca(u,k)!=k){
            cout<<"escaped"<<endl;
        }
        else{
            // cout<<"-1"<<endl;
            int res = qry(u,k) + dist[u];
            if(res<=inf){
                cout<<res<<endl;
            }
            else{
                cout<<"oo"<<endl;
            }
        }



    }

}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        fast();
    }
 
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(long long int, long long int)':
valley.cpp:34:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for(auto [v,w]:graph[node]){
      |              ^
valley.cpp: In function 'void dps(long long int, long long int)':
valley.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for(auto [v,w]:graph[node]){
      |              ^
valley.cpp: In function 'void fast()':
valley.cpp:126:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  126 |         auto[ k,v ] = edge[idx];
      |             ^

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