Submission #955216

#	Time	Username	Problem	Language	Result	Execution time	Memory
955216		JakobZorz	Valley (BOI19_valley)	C++17	100 / 100	166 ms	44788 KiB

valley

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
#include<random>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;

int n,s,q,root;
bool has_shop[100000];
vector<pair<int,int>>nodes[100000];
vector<pair<int,int>>conns;
int par[100000][20];
int depth[100000];
ll depthw[100000];
ll nrd1[100000],nrd2[100000];
int nrc1[100000],nrc2[100000];
ll nru[100000][20];

void dfs1(int node){
    for(int i=1;i<20;i++)
        par[node][i]=par[par[node][i-1]][i-1];
    nrc1[node]=-1;
    nrc2[node]=-1;
    nrd1[node]=1e18;
    nrd2[node]=1e18;
    if(has_shop[node])
        nrd1[node]=0;
    for(auto[ne,w]:nodes[node]){
        if(ne==par[node][0])
            continue;
        par[ne][0]=node;
        depth[ne]=depth[node]+1;
        depthw[ne]=depthw[node]+w;
        dfs1(ne);
        if(nrd1[ne]+w<nrd1[node]){
            nrc2[node]=nrc1[node];
            nrd2[node]=nrd1[node];
            nrd1[node]=nrd1[ne]+w;
            nrc1[node]=ne;
        }else if(nrd1[ne]+w<nrd2[node]){
            nrd2[node]=nrd1[ne]+w;
            nrc2[node]=ne;
        }
    }
}

void dfs2(int node){
    for(auto[ne,w]:nodes[node]){
        if(ne==par[node][0])
            continue;
        if(nrc1[node]==ne)
            nru[ne][0]=w+nrd2[node];
        else
            nru[ne][0]=w+nrd1[node];
        for(int i=1;i<20;i++)
            nru[ne][i]=min(nru[ne][i-1],nru[par[ne][i-1]][i-1]+depthw[ne]-depthw[par[ne][i-1]]);
        dfs2(ne);
    }
}

int get_par(int node,int up){
    for(int i=19;i>=0;i--)
        if(up&(1<<i))
            node=par[node][i];
    return node;
}


// is a sub b?
bool is_sub(int a,int b){
    return depth[a]>=depth[b]&&get_par(a,depth[a]-depth[b])==b;
}

void solve(){
    cin>>n>>s>>q>>root;
    root--;
    for(int i=1;i<n;i++){
        int a,b,w;
        cin>>a>>b>>w;
        a--;b--;
        nodes[a].emplace_back(b,w);
        nodes[b].emplace_back(a,w);
        conns.emplace_back(a,b);
    }
    for(int i=0;i<s;i++){
        int a;
        cin>>a;
        has_shop[a-1]=true;
    }
    par[root][0]=root;
    dfs1(root);
    dfs2(root);
    while(q--){
        int bc,node;
        cin>>bc>>node;
        node--;bc--;
        int bn=conns[bc].first;
        if(par[conns[bc].second][0]==conns[bc].first)
            bn=conns[bc].second;
        if(!is_sub(node,bn)){
            cout<<"escaped\n";
            continue;
        }
        
        ll res=nrd1[node];
        ll len=0;
        for(int p=19;p>=0;p--){
            if((1<<p)<=depth[node]-depth[bn]){
                res=min(res,nru[node][p]+len);
                len+=depthw[node];
                node=par[node][p];
                len-=depthw[node];
            }
        }
        
        if(res>=1e18)
            cout<<"oo\n";
        else
            cout<<res<<"\n";
    }
}
 
int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("/Users/jakob/cp_testing/test.txt","r",stdin);freopen("output.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}
 
/*

5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5

escaped
3
oo
 
 
10 2 5 4
7 2 3
4 8 3
9 10 1
6 7 3
9 2 3
10 1 2
8 2 2
5 2 1
3 8 2
8
7
2 1
1 5
8 4
6 2
7 7

8
escaped
esacped
escaped
0

*/

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