제출 #1194156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194156		Hamed_Ghaffari	Valley (BOI19_valley)	C++20	100 / 100	110 ms	40204 KiB

valley

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

using ll = long long;
using pii = pair<int, int>;

#define X first
#define Y second

const int MXN = 1e5+5;
const int LOG = 17;
const ll inf = 1e18;

int par[MXN][LOG], W[MXN], n, down[MXN];
vector<pii> g[MXN];
bool shop[MXN];
ll dp[MXN], mn[MXN][LOG], h[MXN], dpth[MXN];
int stt[MXN], fnt[MXN], timer;

void dfs1(int v) {
    for(int i=1; i<LOG; i++)
        par[v][i] = par[par[v][i-1]][i-1];
    stt[v] = timer++;
    dp[v] = shop[v] ? 0 : inf;
    for(auto [u, id] : g[v])
        if(u!=par[v][0]) {
            dpth[u] = dpth[v] + 1;
            par[u][0] = v;
            h[u] = h[v]+W[id];
            down[id] = u;
            dfs1(u);
            dp[v] = min(dp[v], dp[u]+W[id]);
        }
    fnt[v] = timer++;
}

inline bool is_anc(int u, int v) {
    return stt[u] <= stt[v] && fnt[v] <= fnt[u];
}

vector<pii> Q[MXN];

inline void upd(int v, ll x) {
    mn[v][0] = x;
    for(int i=1; i<LOG; i++)
        mn[v][i] = min(mn[v][i-1], mn[par[v][i-1]][i-1]);
}

inline ll get(int v, int d) {
    ll res = inf;
    for(int i=0; i<LOG; i++)
        if(d>>i&1)
            res = min(res, mn[v][i]),
            v = par[v][i];
    return res;
}

ll ans[MXN];

void dfs2(int v) {
    upd(v, dp[v]-h[v]);
    for(auto [e, id] : Q[v])
        ans[id] = get(v, dpth[v]-dpth[down[e]]+1)+h[v];
    if(shop[v]) {
        upd(v, -h[v]);
        for(auto [u, id] : g[v])
            if(u!=par[v][0])
                dfs2(u);
    }
    else {
        ll mn1 = 2*inf, mn2 = 2*inf;
        for(auto [u, id] : g[v])
            if(u!=par[v][0]) {
                ll val = dp[u] + W[id];
                if(val<mn2) mn2 = val;
                if(mn2<mn1) swap(mn1, mn2);
            }
        for(auto [u, id] : g[v])
            if(u!=par[v][0]) {
                if(dp[u] + W[id] == mn1) upd(v, mn2 - h[v]);
                else upd(v, mn1 - h[v]);
                dfs2(u);
            }
    }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int s, e, q;
    cin >> n >> s >> q >> e;
    for(int i=0, u,v,w; i<n-1; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, i+1});
        g[v].push_back({u, i+1});
        W[i+1] = w;
    }
    for(int i=0, c; i<s; i++) {
        cin >> c;
        shop[c] = 1;
    }
    dfs1(e);
    for(int i=0; i<q; i++) {
        int e, r;
        cin >> e >> r;
        if(is_anc(down[e], r))
            Q[r].push_back({e, i});
        else
            ans[i] = -1;
    }
    dfs2(e);
    for(int i=0; i<q; i++)
        if(ans[i]==-1) cout << "escaped\n";
        else if(ans[i]>=inf/10) cout << "oo\n";
        else cout << ans[i] << '\n';
    return 0;
}

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