Submission #720146

#	Time	Username	Problem	Language	Result	Execution time	Memory
720146		Ahmed57	Valley (BOI19_valley)	C++14	100 / 100	482 ms	57360 KiB

valley

#include <bits/stdc++.h>

using namespace std;
#define int long long
long long dis[100001];
bool ch[100001];
long long an[100001];
vector<pair<int,long long>> adj[100001];
int P[100001][17];
pair<long long,long long> V[100001][17];int dep[100001];
void dfs(int i,int pr){
    P[i][0] = pr;
    dep[i] = dep[pr]+1;
    V[i][0] = {an[i]-dis[i],dis[i]};
    for(int j = 1;j<17;j++){
        P[i][j] = P[P[i][j-1]][j-1];
        V[i][j] = min(V[i][j-1],V[P[i][j-1]][j-1]);
    }
    for(auto j:adj[i]){
        if(j.first==pr)continue;
        dis[j.first] = dis[i]+j.second;
        dfs(j.first,i);
    }
}
long long calc(int i,int pr){
    long long ans = (ch[i]?0:1e18);
    for(auto j:adj[i]){
        if(j.first==pr)continue;
        ans = min(ans,calc(j.first,i)+j.second);
    }
    return an[i] = ans;
}
bool can(int no1,int no2){
    if(dep[no1]<dep[no2])return 0;
    for(int j = 16;j>=0;j--){
        if(dep[no1]-dep[no2]>=(1<<j)){
            no1=P[no1][j];
        }
    }
    return no1==no2;
}
pair<long long,long long> lca(long long no1,long long no2){
    pair<long long,long long> ans = {1e18,0};
    for(int j = 16;j>=0;j--){
        if(dep[no1]-dep[no2]+1>=(1<<j)){
            ans = min(ans,V[no1][j]);
            no1=P[no1][j];
        }
    }
    return ans;
}
signed main(){
    an[0]= 1e18;
    int n,s,q,e;
    cin>>n>>s>>q>>e;
    vector<pair<long long,long long>> v;
    for(int i = 0;i<n-1;i++){
        long long a,b,c;cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
        v.push_back({a,b});
    }
    for(int i = 0;i<s;i++){
        int x;cin>>x;ch[x] = 1;
    }
    calc(e,1);
    dfs(e,1);
    for(int i = 0;i<v.size();i++){
        if(dep[v[i].first]>dep[v[i].second])swap(v[i].first,v[i].second);
    }
    while(q--){
        int blo,nod;cin>>blo>>nod;
        blo = v[blo-1].second;
        if(can(nod,blo)){
            pair<long long,long long> val = lca(nod,blo);
            if(val.first>=1e16){
                cout<<"oo"<<endl;
            }else{
                cout<<val.first+val.second+(dis[nod]-val.second)<<endl;
            }
        }else cout<<"escaped"<<endl;
    }
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:68:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~

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