제출 #866872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
866872		sleepntsheep	Valley (BOI19_valley)	C++17	36 / 100	3038 ms	23044 KiB

valley

#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 200005
#define ALL(x) x.begin(), x.end()

int n, s, e, q, in[N], out[N], timer, P[N], J[N], L[N];
vector<tuple<int, int, int>> el;
vector<pair<int, int>> g[N];
ll dp[N], dp2[N], O[N];

void dfs0(int u, int p)
{
    P[u] = p; L[u] = L[p]+1;
    in[u] = timer++;
    for (auto [w, v] : g[u]) if (v != p) dp2[v] = dp2[u] + w, dfs0(v, u), dp[u] = min(dp[u], w + dp[v]);
    out[u] = timer++;
    if (L[p] - L[J[p]] == L[J[p]] - L[J[J[p]]])
        J[u] = J[J[p]], O[u] = min({dp[u] - dp2[u], O[p], O[J[p]]});
    else J[u] = p, O[u] = dp[u] - dp2[u];
}

void init()
{
    ShinLena;
    cin >> n >> s >> q >> e;
    memset(dp, 63, sizeof dp), memset(O, 63, sizeof O);
    el.resize(n-1);
    for (auto &[u, v, w] : el) cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u);
    for (int i = 0, c; i < s; ++i) cin >> c, dp[c] = 0;
    L[0] = -2; J[e] = e; dfs0(e, 0);
}

void answer()
{
    for (int i, u; q--;)
    {
        cin >> i >> u;
        int v = get<0>(el[i-1]) == u ? get<1>(el[i-1]) : get<0>(el[i-1]), v2 = get<0>(el[i-1]) == v ? get<1>(el[i-1]) : get<0>(el[i-1]);
        if (P[v2] == v) swap(v, v2);
        if (in[v] <= in[u] && out[u] <= out[v])
        {
            ll z = min(dp[u], dp[v] - dp2[v] + dp2[u]), u0 = u;
            for (; L[u] > L[v];)
            {
                if (L[J[u]] < L[v]) z = min(z, dp2[u0] + dp[u] - dp2[u]), u = P[u];
                else z = min(z, dp2[u0] + O[u]), u = J[u];
            }
            (z < 1e15 ? (cout << z << '\n') : cout << "oo\n");
        }
        else cout << "escaped\n";
    }
}

signed main()
{
    init();
    answer();
    return 0;
}

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