제출 #556683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556683		jasmin	Valley (BOI19_valley)	C++14	0 / 100	180 ms	50748 KiB

valley

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

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

struct graph{
    vector<vector<pair<int,int> > > adi;
    vector<bool> shop;
    vector<vector<int> > up;
    vector<vector<int> > dist;
    vector<vector<int> > abst;
    vector<int> pre;
    vector<int> post;
    int t=0;

    graph(int n){
        adi.resize(n);
        shop.resize(n);
        up.resize(n, vector<int> (l, -1));
        dist.resize(n, vector<int> (l, inf));
        abst.resize(n, vector<int> (l));
        pre.resize(n);
        post.resize(n);
    }

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

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

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

        for(auto u: adi[v]){
            dist[u.first][0]=min(dist[u.first][0], dist[v][0]+u.second);
        }

        post[v]=t; t++;
    }
    void dfs2(int v, int p, int d){
        up[v][0]=p;
        abst[v][0]=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];
            abst[v][i]=abst[up[v][i-1]][i-1]+abst[v][i-1];
        }
        for(int i=1; i<l; i++){
            if(up[v][i-1]==-1) break;
            dist[v][i]=min(dist[v][i-1], dist[up[v][i-1]][i-1]+abst[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 pre[a]<=pre[b] && post[b]<=post[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);
    vector<pair<int,int> > edge;
    for(int i=0; i<n-1; i++){
        int a, b, c;
        cin >> a >> b >> c; 
        g.adi[a-1].push_back({b-1, c});
        g.adi[b-1].push_back({a-1, c});
        edge.push_back({a-1, b-1});
    }
    for(int i=0; i<s; i++){
        int a;
        cin >> a;
        g.shop[a-1]=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(edge[x].second, edge[x].first)){
            swap(edge[x].first, edge[x].second);
        }

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

        int h=g.pre[edge[x].second];
        int ans=inf;
        int a=0;
        for(int i=l-1; i>=0; i--){
            if(g.up[r][i]==-1) continue;
            if(h<=g.pre[g.up[r][i]]){
                ans=min(ans, g.dist[r][i]+a);
                a+=g.abst[r][i];
                r=g.up[r][i];
            }
        }
        if(ans==inf){
            cout << "oo\n";
        }
        else{
            cout << ans << "\n";
        }
    }
}

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