Submission #643705

#	Time	Username	Problem	Language	Result	Execution time	Memory
643705		ParsaS	Valley (BOI19_valley)	C++14	100 / 100	474 ms	81492 KiB

valley

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
#define int ll
const int N = 1e5 + 5, MOD = 1e9 + 7, L = 22, inf = 1e18;
int n, s, q, E;
vector<pair<int, int> > adj[N];
bool shop[N];
pair<int, int> edge[N];

int h[N], up[N][L], tin[N], tout[N], T;
ll dis[N], dpDown[N], mn2[N], dpUp[N];
ll up2[2][N][L];
int mn[N];


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

int lca(int v, int u) {
    if (tin[v] < tin[u])
        swap(v, u);
    if (anc(v, u))
        return v;
    for (int l = L - 1; l >= 0; l--) {
        if (!anc(up[v][l], u))
            v = up[v][l];
    }
    return up[v][0];
}
ll DIS(int v, int u) {
    if (v == 0 || u == 0)
        return inf;
    return dis[v] + dis[u] - 2 * dis[lca(v, u)];
}

void dfs(int v, int p) {
    tin[v] = ++T;
    up[v][0] = p;
    for (int l = 1; l < L; l++)
        up[v][l] = up[up[v][l - 1]][l - 1];
    dpDown[v] = 0;
    if (shop[v]) {
        dpDown[v] = v;
    }

    for (auto [u, w] : adj[v]) {
        if (u == p)
            continue;
        dis[u] = dis[v] + w;
        h[u] = h[v] + 1;
        dfs(u, v);
        if (DIS(dpDown[u], v) < DIS(dpDown[v], v))
            dpDown[v] = dpDown[u];
    }
    tout[v] = ++T;
}

void dfs2(int v, int p) {
    up2[0][v][0] = mn2[p] - dis[p];
    up2[1][v][0] = mn2[p] + dis[p];
    for (int l = 1; l < L; l++) {
        up2[0][v][l] = min(up2[0][v][l - 1], up2[0][up[v][l - 1]][l - 1]);
        up2[1][v][l] = min(up2[1][v][l - 1], up2[1][up[v][l - 1]][l - 1]);
    }

    mn[v] = dpDown[v];
    mn2[v] = inf;
    if (DIS(dpDown[v], v) > DIS(dpUp[v], v))
        mn[v] = dpUp[v];

    for (auto [u, w] : adj[v]) {
        if (u == p)
            continue;
        if (mn[v] != dpDown[u]) {
            mn2[v] = min(mn2[v], DIS(dpDown[u], v));
        }
    }
    if (mn[v] != dpUp[v]) {
        mn2[v] = min(mn2[v], DIS(dpUp[v], v));
    }
    int tmp1 = 0, tmp2 = 0;
    for (auto [u, w] : adj[v]) {
        if (u == p)
            continue;
        if (DIS(tmp1, v) > DIS(dpDown[u], v))
            tmp2 = tmp1, tmp1 = dpDown[u];
        else if (DIS(tmp2, v) > DIS(dpDown[u], v))
            tmp2 = dpDown[u];
    }
    if (DIS(dpUp[v], v) < DIS(tmp1, v))
        tmp2 = tmp1, tmp1 = dpUp[v];
    else if (DIS(dpUp[v], v) < DIS(tmp2, v))
        tmp2 = dpUp[v];
    if (shop[v]) {
        tmp1 = v;
    }

    for (auto [u, w] : adj[v]) {
        if (u == p)
            continue;

        if (tmp1 != dpDown[u]) {
            dpUp[u] = tmp1;
        }
        else
            dpUp[u] = tmp2;
        dfs2(u, v);
    }

}
bool in_path(int v, int u, int x, int y) {
    if (tin[x] > tin[y])
        swap(x, y);
    int l = lca(v, u);
    return anc(l, x) && (anc(y, v) || anc(y, u));
}
ll minUp(int t, int v, int len) {
    ll ans = inf;
    for (int i = 0; i < L; i++) {
        if (len & (1 << i)) {
            ans = min(ans, up2[t][v][i]);
            v = up[v][i];
        }
    }
    return ans;
}


void solve() {
    cin >> n >> s >> q >> E;
    for (int i = 0; i < n - 1; i++) {
        int v, u, w; cin >> v >> u >> w;
        adj[v].pb(mp(u, w));
        adj[u].pb(mp(v, w));
        edge[i] = mp(v, u);
    }
    int r = 1;
    for (int i = 0; i < s; i++) {
        int v; cin >> v;
        shop[v] = true;
    }
    dfs(r, 0);
    tout[0] = 1e9;
    mn2[0] = inf;
    for (int i = 0; i < L; i++)
        up2[0][0][i] = up2[1][0][i] = inf;
    dfs2(r, 0);

    while (q--) {
        int i, v; cin >> i >> v;
        --i;
        int x = edge[i].fi, y = edge[i].se;
        if (tin[x] > tin[y])
            swap(x, y);

        int l = lca(v, E);
        if (!in_path(v, E, x, y)) {
            cout << "escaped\n";
            continue;
        }
        l = lca(v, mn[v]);
        if (!in_path(v, mn[v], x, y)) {
            cout << DIS(v, mn[v]) << '\n';
            continue;
        }
        int u = mn[v];
        if (v == l) {
            ll val = min(mn2[x] + dis[x], minUp(1, x, h[x] - h[v]));
            if (val <= 1e17) {
                cout << val - dis[v] << '\n';
                continue;
            }
        }
        else if (in_path(l, v, x, y)) {
            ll val = min(mn2[v] - dis[v], minUp(0, v, h[v] - h[y]));
            if (val <= 1e17) {
                cout << val + dis[v] << '\n';
                continue;
            }
        }
        else {
            ll val1 = min(mn2[v] - dis[v], minUp(0, v, h[v] - h[l])) + dis[v];
            ll val2 = min(mn2[x] + dis[x], minUp(1, x, h[x] - h[l])) - dis[l] + dis[v] - dis[l];

            if (min(val1, val2) <= 1e17) {
                cout << min(val1, val2) << '\n';
                continue;
            }
        }
        cout << "oo" << '\n';
    }
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();

    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(ll, ll)':
valley.cpp:53:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     for (auto [u, w] : adj[v]) {
      |               ^
valley.cpp: In function 'void dfs2(ll, ll)':
valley.cpp:78:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |     for (auto [u, w] : adj[v]) {
      |               ^
valley.cpp:89:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |     for (auto [u, w] : adj[v]) {
      |               ^
valley.cpp:105:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |     for (auto [u, w] : adj[v]) {
      |               ^
valley.cpp: In function 'void solve()':
valley.cpp:173:13: warning: unused variable 'u' [-Wunused-variable]
  173 |         int u = mn[v];
      |             ^

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