Submission #1158560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158560		AlgorithmWarrior	Valley (BOI19_valley)	C++20	100 / 100	113 ms	37128 KiB

valley

#include <bits/stdc++.h>

using namespace std;

int const MAX=1e5+5;
int const LOG=20;
long long const INF=1e18;
int n,nrs,q,root;
struct edge{
    int nod,len;
};
struct muchie{
    int a,b;
}much[MAX];
vector<edge>tree[MAX];
int ancestor[MAX][LOG];
long long dist_shop[MAX][LOG];
bool shop[MAX];
long long nearest_sub[MAX];
long long dist_rt[MAX];
int niv[MAX];

void read(){
    cin>>n>>nrs>>q>>root;
    int i;
    for(i=1;i<n;++i){
        int a,b,w;
        cin>>a>>b>>w;
        tree[a].push_back({b,w});
        tree[b].push_back({a,w});
        much[i]={a,b};
    }
    for(i=1;i<=nrs;++i){
        int sh;
        cin>>sh;
        shop[sh]=1;
    }
}

void minself(long long& x,long long val){
    if(x>val)
        x=val;
}

long long dfs(int nod){
    if(shop[nod])
        nearest_sub[nod]=0;
    else
        nearest_sub[nod]=INF;
    for(auto edg : tree[nod]){
        int fiu=edg.nod;
        int w=edg.len;
        if(fiu!=ancestor[nod][0]){
            ancestor[fiu][0]=nod;
            niv[fiu]=niv[nod]+1;
            dist_rt[fiu]=dist_rt[nod]+w;
            minself(nearest_sub[nod],w+dfs(fiu));
        }
    }
    return nearest_sub[nod];
}

long long dist(int nod,int anc){
    return dist_rt[nod]-dist_rt[anc];
}

void get_rmq(){
    int i,j;
    for(i=1;i<=n;++i){
        int tata=ancestor[i][0];
        dist_shop[i][0]=dist(i,tata)+nearest_sub[tata];
    }
    for(j=1;j<LOG;++j)
        for(i=1;i<=n;++i){
            int anc=ancestor[i][j-1];
            dist_shop[i][j]=dist_shop[i][j-1];
            if(anc)
                minself(dist_shop[i][j],dist(i,anc)+dist_shop[anc][j-1]);
            ancestor[i][j]=ancestor[anc][j-1];
        }
}

struct to_anc{
    int anc;
    long long ans;
};

to_anc lift(int nod,int lev){
    long long ans=INF;
    long long dst=0;
    int anc=nod;
    int i;
    for(i=0;i<LOG;++i)
        if(lev&(1<<i)){
            minself(ans,dst+dist_shop[anc][i]);
            dst+=dist(anc,ancestor[anc][i]);
            anc=ancestor[anc][i];
        }
    return {anc,ans};
}

void solve(int nod,int anc){
    if(niv[nod]<niv[anc]){
        cout<<"escaped\n";
        return;
    }
    int ances;
    long long ans;
    to_anc rasp;
    rasp=lift(nod,niv[nod]-niv[anc]);
    ances=rasp.anc;
    ans=rasp.ans;
    if(ances!=anc){
        cout<<"escaped\n";
        return;
    }
    minself(ans,nearest_sub[nod]);
    if(ans==INF){
        cout<<"oo\n";
        return;
    }
    cout<<ans<<'\n';
}

void process_queries(){
    int i;
    for(i=1;i<=q;++i){
        int id_e,nod;
        cin>>id_e>>nod;
        int anc;
        int a,b;
        a=much[id_e].a;
        b=much[id_e].b;
        if(a==ancestor[b][0])
            anc=b;
        else
            anc=a;
        solve(nod,anc);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    dfs(root);
    get_rmq();
    process_queries();
    return 0;
}

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