제출 #1330673

#제출 시각아이디문제언어결과실행 시간메모리
1330673wedonttalkanymoreValley (BOI19_valley)C++20
100 / 100
208 ms51020 KiB
#include <bits/stdc++.h>
/*
    Chang ki si xuyen man dem
    Di lac vao trong giac mong
*/
using namespace std;
using ll = long long;

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 5e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 19;

int n, q, s, E;
vector <pii> adj[N];
int c[N]; // exist shop or not
int in[N], out[N], tdfs;
int h[N], dp[N], dp1[N];
// dp[anc] is min of h[v] - 2 * h[anc] while dp1[anc] is min of h[v]
int st[N][lim + 1], W[N][lim + 1]; // W[i][0] = min(dp[i])
pii edge[N];
int dist[N];

void dfs(int u, int par) { // preprocess
    in[u] = out[u] = ++tdfs;
    if (c[u]) dp1[u] = dist[u];
    else dp1[u] = inf;
    for (auto [v, w] : adj[u]) {
        if (v != par) {
            h[v] = h[u] + 1;
            dist[v] = dist[u] + w;
            dfs(v, u);
            dp1[u] = min(dp1[u], dp1[v]);
        }
    }
    out[u] = tdfs;
    if (dp1[u] != inf) dp[u] = dp1[u] - 2 * dist[u];
    else dp[u] = inf;
}

void dfs1(int u, int par) { // build binary lifting
    st[u][0] = par;
    W[u][0] = dp[u];
    for (int i = 1; i <= lim; i++) {
        st[u][i] = st[st[u][i - 1]][i - 1];
        W[u][i] = min(W[u][i - 1], W[st[u][i - 1]][i - 1]);
    }
    for (auto [v, w] : adj[u]) {
        if (v != par) {
            dfs1(v, u);
        }
    }
}

bool check(int u, int v) { // check if v in subtree u
    return in[u] <= in[v] && out[v] <= out[u];
}

void solve() {
    dfs(E, 0);
    for (int i = 0; i <= lim; i++) {
        st[0][i] = 0;
        W[0][i] = inf;
    }
    dfs1(E, 0);
    // cout << h[3] << ' ' << dp1[3] << W[5][0] << '\n';
    for (int i = 1; i <= q; i++) {
        int id, R;
        cin >> id >> R;
        int u = edge[id].fi, v = edge[id].se;
        int low_edge = u;
        if (in[u] < in[v]) low_edge = v; // the node lower than other node
        // if (i == 2) cout << low_edge << ' ' << R << ' ' << check(low_edge, R) << '\n';
        if (!check(low_edge, R)) { // R can connect with E
            cout << "escaped" << '\n';
        }
        else { // R is in the subtree of low_edge
            int t = R;
            int val = inf;
            // cout << "now: " << h[t] << ' ' << h[low_edge] << '\n';
            for (int j = lim; j >= 0; j--) {
                if (h[t] - (1 << j) < h[low_edge]) continue;
                val = min(val, W[t][j]);
                // cout << t << ' ';
                t = st[t][j];
            }
            // cout << "at1: " << t << '\n';
            val = min(val, dp[t]);
            // cout << "at: " << val << '\n';
            if (val == inf) cout << "oo" << '\n';
            else cout << dist[R] + val << '\n';
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    cin >> n >> s >> q >> E;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[i] = make_pair(u, v);
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    for (int i = 1; i <= s; i++) {
        int x;
        cin >> x;
        c[x] = 1;
    }
    solve();
    return 0;
}

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

valley.cpp: In function 'int main()':
valley.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
valley.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(".out", "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...