제출 #1334144

#제출 시각아이디문제언어결과실행 시간메모리
1334144adscodingValley (BOI19_valley)C++20
100 / 100
112 ms38592 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e15;
const int MAXN = 1e5 + 5;

struct Edge { int to, weight, id; };
vector<Edge> adj[MAXN];
pair<int, int> edges[MAXN];
int tin[MAXN], tout[MAXN], timer;
int up[MAXN][20];
ll dist[MAXN], close_shop[MAXN], best[MAXN][20];
bool has_shop[MAXN];
int N, S, Q, E;

void dfs_pre(int u, int p, ll d) {
    tin[u] = ++timer;
    up[u][0] = p;
    dist[u] = d;
    close_shop[u] = has_shop[u] ? d : INF;

    for (auto &e : adj[u]) {
        if (e.to == p) continue;
        dfs_pre(e.to, u, d + e.weight);
        close_shop[u] = min(close_shop[u], close_shop[e.to]);
    }

    best[u][0] = (close_shop[u] == INF) ? INF : (close_shop[u] - 2 * dist[u]);
    tout[u] = timer;
}

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

void solve() {
    cin >> N >> S >> Q >> E;
    for (int i = 1; i < N; ++i) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w, i});
        adj[v].push_back({u, w, i});
        edges[i] = {u, v};
    }
    for (int i = 0; i < S; ++i) { int s; cin >> s; has_shop[s] = true; }

    dfs_pre(E, E, 0);

    for (int j = 1; j < 20; ++j) {
        for (int i = 1; i <= N; ++i) {
            up[i][j] = up[up[i][j - 1]][j - 1];
            best[i][j] = min(best[i][j - 1], best[up[i][j - 1]][j - 1]);
        }
    }

    while (Q--) {
        int idx, R; cin >> idx >> R;
        int u = edges[idx].first, v = edges[idx].second;

        int child = (is_ancestor(u, v)) ? v : u;

        if (!is_ancestor(child, R)) {
            cout << "escaped\n";
        } else {
            ll res = INF;
            int curr = R;

            for (int j = 19; j >= 0; --j) {
                if (is_ancestor(child, up[curr][j])) {
                    res = min(res, best[curr][j]);
                    curr = up[curr][j];
                }
            }
            res = min(res, best[curr][0]);

            if (res >= INF / 2) cout << "oo\n";
            else cout << res + dist[R] << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    #define TASK "TEST"
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".ans", "w", stdout);
    }
    solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp: In function 'int main()':
valley.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(TASK".ans", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...