Submission #928425

#	Time	Username	Problem	Language	Result	Execution time	Memory
928425		Amirreza_Fakhri	Valley (BOI19_valley)	C++17	100 / 100	137 ms	49096 KiB

valley

// In the name of the God
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

const int inf = (1e9+7)*(1e9+7);
const int mod = 998244353;
const int maxn = 1e5+5, lg = 17;

int n, s, q, e, t = 0, fr[maxn], to[maxn], in[maxn], out[maxn], h[maxn], mn[maxn], cost[maxn];
bool mark[maxn];
pii par[lg][maxn];
vector <pii> adj[maxn];

void dfs1(int v, int p) {
    in[v] = t++;
    mn[v] = (!mark[v])*inf;
    for (pii ed : adj[v]) {
        int u = ed.F;
        if (u != p) {
            h[u] = h[v]+1;
            cost[u] = cost[v]+ed.S;
            dfs1(u, v);
            smin(mn[v], ed.S+mn[u]);
        }
    }
    out[v] = t;
}

void dfs2(int v, int p) {
    par[0][v] = mp(p, mn[v]-cost[v]);
    for (int i = 1; i < lg; i++) {
        par[i][v] = mp(par[i-1][par[i-1][v].F].F, min(par[i-1][v].S, par[i-1][par[i-1][v].F].S));
    }
    for (pii ed : adj[v]) {
        int u = ed.F;
        if (u != p) dfs2(u, v);
    }
}

bool is(int v, int u) {
    return in[v] <= in[u] and out[v] >= out[u];
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s >> q >> e; e--;
    for (int i = 1; i < n; i++) {
        int v, u, w; cin >> v >> u >> w;
        adj[--v].pb(mp(--u, w));
        adj[u].pb(mp(v, w));
        fr[i] = v, to[i] = u;
    }
    for (int i = 0; i < s; i++) {
        int v; cin >> v; mark[--v] = 1;
    }
    dfs1(e, e), dfs2(e, e);
    while (q--) {
        int i, v; cin >> i >> v; v--;
        int u = fr[i], z = to[i];
        if (in[u] > in[z]) swap(u, z);
        if (!is(z, v)) cout << "escaped\n";
        else {
            int ans = inf, d = cost[v], diff = (h[v]-h[u]);
            for (int i = 0; i < lg; i++) {
                if (diff&(1<<i)) {
                    smin(ans, d+par[i][v].S);
                    v = par[i][v].F;
                }
            }
            if (ans == inf) cout << "oo\n";
            else cout << ans << '\n';
        }
    }
    return 0;
}

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