Submission #527755

#	Time	Username	Problem	Language	Result	Execution time	Memory
527755		jalsol	Valley (BOI19_valley)	C++11	100 / 100	162 ms	36376 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#define Task ""

struct __Init__ {
    __Init__() {
        cin.tie(nullptr)->sync_with_stdio(false);
        if (fopen(Task".inp", "r")) {
            freopen(Task".inp", "r", stdin);
            freopen(Task".out", "w", stdout); }
    }
} __init__;

using ll = long long;

#ifdef LOCAL
#define debug(x) cerr << "[" #x " = " << x << "]\n";
#else
#define debug(...)
#endif // LOCAL

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)

template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxN = 1e5 + 5;
constexpr int logN = 18;

struct Edge {
    int u, v, c;

    int other(int x) const {
        return u ^ v ^ x;
    }
};

int n, ns, nq, root;
vector<int> g[maxN];
Edge e[maxN];

int tin[maxN], tout[maxN], timer;
int par[maxN][logN];
int dep[maxN];
ll st[maxN][logN];
ll dist[maxN];
ll dp[maxN];

void Dfs(int u) {
    tin[u] = ++timer;

    for (int i : g[u]) {
        int v = e[i].other(u);

        if (v != par[u][0]) {
            dist[v] = dist[u] + e[i].c;
            dep[v] = dep[u] + 1;
            par[v][0] = u;

            Dfs(v);

            chmin(dp[u], dp[v] + e[i].c);
        }
    }

    tout[u] = ++timer;
}

bool isAnc(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

signed main() {
    cin >> n >> ns >> nq >> root;

    For (i, 1, n - 1) {
        int u, v, c; cin >> u >> v >> c;
        e[i] = {u, v, c};
        g[u].push_back(i);
        g[v].push_back(i);
    }

    For (i, 1, n) dp[i] = linf;

    For (i, 1, ns) {
        int x; cin >> x;
        dp[x] = 0;
    }

    Dfs(root);

    For (i, 1, n) {
        st[i][0] = dp[i] - dist[i];
    }

    For (j, 1, logN - 1) {
        For (i, 1, n) {
            int m = par[i][j - 1];
            par[i][j] = par[m][j - 1];
            st[i][j] = min(st[i][j - 1], st[m][j - 1]);
        }
    }

    Rep (_, nq) {
        int id, x; cin >> id >> x;

        int u = e[id].u;
        int v = e[id].v;
        if (tin[u] > tin[v]) swap(u, v);

        if (!isAnc(v, x)) {
            cout << "escaped\n";
            continue;
        }

        ll ans = linf;
        int step = dep[x] - dep[v] + 1;
        u = x;

        Repd (i, logN) {
            if (step >> i & 1) {
                chmin(ans, st[u][i]);
                u = par[u][i];
            }
        }

        ans += dist[x];

        if (ans >= linf) {
            cout << "oo\n";
        } else {
            cout << ans << '\n';
        }
    }
}

/*

*/

Compilation message (stderr)

valley.cpp: In constructor '__Init__::__Init__()':
valley.cpp:11:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |             freopen(Task".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:12:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             freopen(Task".out", "w", stdout); }
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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