제출 #1305734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305734		Sofiatpc	Valley (BOI19_valley)	C++20	100 / 100	150 ms	67204 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define sz(v) (int)v.size()
const int MAXN = 1e5+5, MAX = 16, INF = 1e16;
vector<int> adj[MAXN], w[MAXN], id[MAXN];
int perto[MAXN], rep[MAXN], tin[MAXN], tout[MAXN], t;
int jump[MAX+5][MAXN], mn[MAX+5][MAXN], sp[MAX+5][MAXN];

void dfs(int s, int p){
    tin[s] = ++t;
    for(int i = 0; i < sz(adj[s]); i++){
        int viz = adj[s][i];
        if(viz == p)continue;

        dfs(viz,s);
        perto[s] = min(perto[s], perto[viz] + w[s][i]);
        rep[ id[s][i] ] = viz;
    }

    for(int i = 0; i < sz(adj[s]); i++){
        int viz = adj[s][i];
        if(viz != p){
            jump[0][viz] = s;
            mn[0][viz] = min(perto[viz], perto[s] + w[s][i]);
            sp[0][viz] = w[s][i];
        }
    }
    tout[s] = t;
}

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

    int n,s,q,e; cin>>n>>s>>q>>e;

    for(int i = 0; i <= MAX; i++)
        for(int j = 1; j <= n; j++)mn[i][j] = INF;

    for(int i = 1; i < n; i++){
        int a,b,c; cin>>a>>b>>c;
        adj[a].push_back(b); w[a].push_back(c); id[a].push_back(i);
        adj[b].push_back(a); w[b].push_back(c); id[b].push_back(i);
    }

    for(int i = 1; i <= n; i++)perto[i] = INF;

    for(int i = 1; i <= s; i++){
        int c; cin>>c;
        perto[c] = 0;
    }

    dfs(e,0);

    for(int i = 1; i <= MAX; i++)
        for(int j = 1; j <= n; j++){
            if(jump[i-1][j] != 0){
                jump[i][j] = jump[i-1][ jump[i-1][j] ];
                sp[i][j] = sp[i-1][j] + sp[i-1][ jump[i-1][j] ];
                mn[i][j] = min(mn[i-1][j], mn[i-1][ jump[i-1][j] ] + sp[i-1][j]);
            }
        }

    while(q--){
        int i,v; cin>>i>>v;
        int b = rep[i];
        if(tin[b] <= tin[v] && tin[v] <= tout[b]){
            int ans = perto[v], s = 0;
            for(int j = MAX; j >= 0; j--){
                if( tin[ jump[j][v] ] >= tin[b]){
                    ans = min(ans, mn[j][v]+s);
                    s += sp[j][v];
                    v = jump[j][v];
                }
            }


            if(ans == INF)cout<<"oo\n";
            else cout<<ans<<"\n";
        }else cout<<"escaped\n";

    }
}   

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