Submission #1104722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104722		29ChuManhTich	Valley (BOI19_valley)	C++17	100 / 100	114 ms	50500 KiB

valley

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

#define NAME "FOX"
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define ii pair<int, int>
#define fi first
#define se second
#define choanh1chuthivongduockhong ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                                                    \
    cout.tie(NULL);
#define BIT(x, i) ((x >> i) & 1)
#define ALL(x) x.begin(), x.end()

const int maxn = 1e5 + 11;
const int LOGN = 20;
const int INF = 1e18;

int par[maxn][LOGN], mi[maxn][LOGN], dp[maxn], dis[maxn], tin[maxn], tout[maxn], ds[maxn], timedfs;
int n, s, q, h;
vector<ii> adj[maxn];
ii edge[maxn];

void dfs(int u, int p = -1) {
    tin[u] = ++timedfs;
    for(ii i : adj[u]) {
        int v = i.se;
        int w = i.fi;
        if(v == p) continue;
        ds[v] = ds[u] + 1;
        dis[v] = dis[u] + w;
        dfs(v, u);
        dp[u] = min(dp[u], dp[v] + w);
        par[v][0] = u;
    }
    if(dp[u] != INF) mi[u][0] = dp[u] - dis[u];
    tout[u] = timedfs;
}

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

int calc(int u, int len) {
    int res = INF;
    FOD(k, LOGN - 1, 0) {
        if((1 << k) <= len) {
            len -= (1 << k);
            res = min(res, mi[u][k]);
            u = par[u][k];
        }
    }
    return res;
}

signed main() {
    if(fopen(NAME".INP", "r")) {
        freopen(NAME".INP", "r", stdin);
        freopen(NAME".OUT", "w", stdout);
    }
    choanh1chuthivongduockhong;
    cin >> n >> s >> q >> h;

    FOR(i, 1, n - 1) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});
        edge[i] = {u, v};
    }

    FOR(i, 1, n) {
        dp[i] = INF;
        mi[i][0] = INF;
    }

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

    dfs(h);

    FOR(k, 1, LOGN - 1) {
        FOR(i, 1, n) {
            par[i][k] = par[par[i][k - 1]][k - 1];
            mi[i][k] = min(mi[i][k - 1], mi[par[i][k - 1]][k - 1]);
        }
    }

    while(q--) {
        int i, r;
        cin >> i >> r;
        if(ds[edge[i].fi] > ds[edge[i].se]) swap(edge[i].fi, edge[i].se);
        if(!in(edge[i].se, r)) {
            cout << "escaped\n";
            continue;
        }
        int res = dis[r] + calc(r, ds[r] - ds[edge[i].se] + 1);
        if(res >= INF) {
            cout << "oo\n";
        } else {
            cout << res << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(NAME".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(NAME".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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