Submission #1132926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132926		hungandhimself	Valley (BOI19_valley)	C++20	0 / 100	122 ms	42352 KiB

valley

#include <bits/stdc++.h>
using namespace std;
 #define int long long
#define ll long long
#define lint long long int
#define debugi(i, f) cerr << "i = " << i << " : f[i] = " << f[i] << "\n";
#define debugii(i, j, f) cerr << "i = " << i << " and j = " << j << " : f[i][j] = " << f[i][j] << "\n";
#define debugiii(i, j, k, f) cerr << "i = " << i << " and j = " << j << " and k = " << k << " : f[i][j][k] = " << f[i][j][k] << "\n";
#define vc vector
#define pr pair
#define ii pair<int, int>
#define iii pair<int, ii>
#define fi first
#define se second
#define Pi 3.1415926535897932384
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll mod = 1e9 + 7;
const int MOD = 2e9 + 33;
const int N = 1e5 + 2;


int n, s, q, e;
vc<ii> adj[N];
ii edges[N];
bool mark[N];

namespace biLifting {
    int h[N], anc[N][19], dist[N], jumpMg[N][19], mg[N];
    void dfs (int node, int prenode) {
        if (mark[node] == true) mg[node] = dist[node];
        else mg[node] = 1e18;
        for (ii x : adj[node]) if (x.fi != prenode) {
            h[x.fi] = h[node] + 1;
            dist[x.fi] = dist[node] + x.se;
            anc[x.fi][0] = node;
            dfs(x.fi, node);
            mg[node] = min(mg[node], mg[x.fi]);
        }
    }

    void computeMg () {
        for (int i = 1; i <= n; i++) if (mg[i] != 1e18) {
            mg[i] -= 2 * dist[i];
        }
    }

    void preCal () {
        for (int i = 1; i <= n; i++) {
            jumpMg[i][0] = min(mg[i], mg[anc[i][0]]);
        }

        for (int j = 1; (1 << j) <= n; j++) {
            for (int i = 1; i <= n; i++) {
                anc[i][j] = anc[anc[i][j - 1]][j - 1];
                jumpMg[i][j] = min(jumpMg[i][j - 1], jumpMg[anc[i][j - 1]][j - 1]);
            }
        }
    }

    int lca (int u, int v) {
        if (h[u] < h[v]) swap(u, v);
        int diff = h[u] - h[v];
        for (int mask = 0; (1 << mask) <= diff; mask++) {
            if (diff & (1 << mask)) {
                u = anc[u][mask];
            }
        }

        if (u == v) return u;
        int lg = log2(h[u]);
        for (int mask = lg; mask >= 0; mask--) {
            if (anc[u][mask] != anc[v][mask]) {
                u = anc[u][mask];
                v = anc[v][mask];
            }
        }

        return anc[u][0];
    }

    int nearestShop (int root, int u) {
        int diff = h[u] - h[root];
//        cout << "diff = " << diff << '\n';
//        cout << "jumpMg[root][0] = " << jumpMg[root][0] << '\n';
        int minMg = 1e18;
        for (int mask = 0, cur = u; (1 << mask) <= diff; mask++) {
            if ((1 << mask) <= diff) {
//                debugii(cur, mask, jumpMg);
                minMg = min(minMg, jumpMg[cur][mask]);
                cur = anc[cur][mask];
            }
        }

//        cout << "minMg = " << minMg << '\n';
        if (minMg == 1e18) return 1e18;
        else return dist[u] + minMg;
    }

    void debug () {
        for (int i = 1; i <= n; i++) {
            for (int j = 0; (1 << j) <= n; j++) {
                debugii(i, j, jumpMg);
            }
        }
    }
}

void runcase (int test) {
    cin >> n >> s >> q >> e;
    for (int i = 2; i <= n; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i - 1].fi = a, edges[i - 1].se = b;
        adj[a].push_back(ii(b, w));
        adj[b].push_back(ii(a, w));
    }

    for (int i = 1; i <= s; i++) {
        int si;
        cin >> si;
        mark[si] = true;
    }

    biLifting::dfs(e, 0), biLifting::computeMg(), biLifting::preCal();
//    biLifting::debug();
    while (q--) {
        int I, R;
        cin >> I >> R;
        int a = edges[I].fi, b = edges[I].se;
        if (biLifting::h[a] > biLifting::h[b])
            swap(a, b);

        int __lca = biLifting::lca(R, b);
//        cout << "lca = " << __lca << '\n';
        if (biLifting::h[__lca] <= biLifting::h[a]) {
            cout << "escaped\n";
            continue;
        }

        int ans = biLifting::nearestShop(b, R);
        if (ans == 1e18) cout << "oo\n";
        else cout << ans << '\n';
    }
}

/**
    B1 : kiểm tra lại code templete, code đã học thuộc
    đọc kĩ đề
    nháp chưa
    kiểm tra lại code, đặc biệt là những chỗ đã học thuộc (nhiều khi sai ở đó)
**/
signed main () {
    ios_base::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    #ifdef ONLINE_JUDGE
        freopen ("runaway.in", "r", stdin);
        freopen ("runaway.out", "w", stdout);
    #else // online submission
    #endif
/// i have a contest soon and i need to learn a much as possible
/// so let become familiar with a bunch of different problems and solution ideas
    // stop learning useless algorithm (with you) and solve more problems
    //Cứ 7 lần nộp thì chỉ được 1 lần sai

    int test = 1;
//    cin >> test;
    while (test--) runcase(test);
    // return 0;
}

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