Submission #556693

#	Time	Username	Problem	Language	Result	Execution time	Memory
556693		jasmin	Valley (BOI19_valley)	C++14	100 / 100	315 ms	65236 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define int long long

int l=25;
const int inf=1e18;

struct graph{
    vector<pair<int,int> > edge;
    vector<vector<pair<int,int> > >adi;
    vector<bool> shop;
    vector<int> tin;
    vector<int> tout;
    vector<int> dist;
    vector<int> down;
    int t=0;

    vector<vector<int> > up;
    vector<vector<int> > best;

    graph(int n){
        edge.resize(n-1);
        adi.resize(n);
        shop.resize(n);
        tin.resize(n);
        tout.resize(n);
        dist.resize(n);
        down.resize(n, inf);
        up.resize(n, vector<int> (l, -1));
        best.resize(n, vector<int> (l, inf));
    }

    void dfs1(int v, int p){
        tin[v]=t; t++;

        if(shop[v]){
            down[v]=0;
        }

        for(auto u: adi[v]){
            if(u.first!=p){
                dist[u.first]=dist[v]+u.second;
                dfs1(u.first, v);
                down[v]=min(down[v], down[u.first]+u.second);
            }
        }

        tout[v]=t; t++;
    }

    void dfs2(int v, int p, int d){
        up[v][0]=p;
        if(p!=-1){
            best[v][0]=min(down[v], down[p]+d);
        }
        for(int i=1; i<l; i++){
            if(up[v][i-1]==-1) break;
            up[v][i]=up[up[v][i-1]][i-1];
            best[v][i]=min(best[v][i-1], best[up[v][i-1]][i-1]+(dist[v]-dist[up[v][i-1]]));
        }

        for(auto u: adi[v]){
            if(u.first!=p){
                dfs2(u.first, v, u.second);
            }
        }
    }

    bool is_ancestor(int a, int b){
        return tin[a]<=tin[b] && tout[b]<=tout[a];
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, s, q, e;
    cin >> n >> s >> q >> e;
    e--;
    graph g(n);
    for(int i=0; i<n-1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g.edge[i]={a, b};
        g.adi[a].push_back({b, c});
        g.adi[b].push_back({a, c});
    }
    for(int i=0; i<s; i++){
        int a;
        cin >> a;
        a--;
        g.shop[a]=true;
    }

    g.dfs1(e, -1);
    g.dfs2(e, -1, 0);

    for(int i=0; i<q; i++){
        int x, r;
        cin >> x >> r;
        x--; r--;

        if(g.is_ancestor(g.edge[x].second, g.edge[x].first)){
            swap(g.edge[x].first, g.edge[x].second);
        }

        //cout << g.edge[x].second << " " << r << "\n";
        if(!g.is_ancestor(g.edge[x].second, r)){
            cout << "escaped\n";
            continue;
        }

        int h=g.tin[g.edge[x].first];
        int ans=g.down[r];
        int a=0;
        for(int j=l-1; j>=0; j--){
            if(g.up[r][j]==-1) continue;
            //cout << r << " " << j << " " << g.up[r][j] << " " << g.tin[g.up[r][j]] <<  " " << h << "\n";
            if(h<g.tin[g.up[r][j]]){
                //cout << "=> " << g.best[r][j] << " " << a << "\n";
                ans=min(ans, g.best[r][j]+a);
                a+=g.dist[r]-g.dist[g.up[r][j]];
                r=g.up[r][j];
            }
        }

        if(ans==inf){
            cout << "oo\n";
        }
        else{
            cout << ans << "\n";
        }
    }
}

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