Submission #1149765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149765		arkanefury	Valley (BOI19_valley)	C++20	23 / 100	311 ms	52712 KiB

valley

#include <bits/stdc++.h>  
#define pb push_back  
using namespace std; 
#define F first
#define S second
#define int long long
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)  
#define FORR(x, n, m, d) for(int x = n; x >= m; x -= d)  
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);  
const int N = 2e5+150;  
const int INF = 1e18;  
int n, m, k, tt, ans, l, r, x, y, cnt, ko = 0; 
int b[N], a[N], sum, lp[N], block = 620, d[N], c[N], up[N][21], par[N], de[N], mn[N][21];
vector<pair<int, int>> g[N];
bool f = 0;

void sol(int v, int p = 0) {
    par[v] = p;
    d[v] = d[p] + 1;
    for (auto i : g[v]) {
        if (p != i.F && v != i.F) {
            de[i.F] = de[v] + i.S;
            sol(i.F, v);
        }
    }
    for (auto i : g[v]) {
        if (i.F != p) lp[v] = min(lp[v], lp[i.F] + i.S);
    }
}

int lca(int x, int y) {
    if (d[x] <= d[y]) swap(x, y);
    FORR(i, 17, 0, 1) if (d[y] <= d[up[x][i]]) x = up[x][i];
    if (x == y) return y;
    FORR(i, 17, 0, 1) if (up[x][i] != up[y][i]) x = up[x][i], y = up[y][i];
    return up[x][0];
}

int jump(int y, int x, int sum = 0, int ans = 0) {
    ans = lp[y];
    FORR(i, 17, 0, 1) {
        if (x >> i & 1) {
            int ko = y;
            ans = min(ans, mn[y][i] + sum), y = up[y][i];
            sum += de[ko] - de[y];
        }
    }
    return ans;
}

void solve() {
    nikita
    int kokain;
    cin >> n >> m >> kokain >> cnt;
    FOR(i, 1, n - 1, 1) {
        cin >> a[i] >> b[i] >> r;
        x = a[i], y = b[i];
        g[x].pb({y, r}), g[y].pb({x, r});
    }
    FOR(i, 1, n, 1) lp[i] = INF;
    FOR(i, 1, m, 1) cin >> c[i], lp[c[i]] = 0;
    sol(cnt);
    lp[0] = INF, de[0] = INF;
    FOR(i, 1, n, 1) up[i][0] = par[i], mn[i][0] = min(lp[i], lp[par[i]] + de[i] - de[par[i]]);
    FOR(i, 1, 17, 1) {
        FOR(j, 1, n, 1) {
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    FOR(i, 1, 17, 1) {
        FOR(j, 1, n, 1) {
            int dist = de[j] - de[up[j][i - 1]];
            mn[j][i] = min(mn[j][i - 1], mn[up[j][i - 1]][i - 1] + dist);
        }
    }
    FOR(i, 1, kokain, 1) {
        cin >> x >> y;
        int lca_ay = lca(a[x], y);
        int lca_by = lca(b[x], y);
        if (lca_ay == a[x] && lca_by == b[x]) {
            if (lp[a[x]] >= INF && lp[b[x]] >= INF) {
                cout << "oo\n";
            } else {
                if (d[b[x]] > d[a[x]]) swap(a[x], b[x]);
                cout << jump(y, d[y] - d[a[x]]) << '\n';
            }
        } else {
            cout << "escaped\n";
        }
    }
}

signed main() {  
    nikita  
    tt = 1;  
    if (!tt) cin >> tt;  
    FOR(i, 1, tt, 1) {  
        solve();  
    }  
}

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