oj.uz

답안 #922715

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
922715 2024-02-06T03:56:10 Z Alihan_8 Valley (BOI19_valley) C++17
23 / 100
 308 ms 64996 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, s, q, rt;
    cin >> n >> s >> q >> rt;
    --rt;

    vector <vector<ar<int,3>>> G(n);

    for ( int i = 0; i + 1 < n; i++ ){
        int u, v, w; cin >> u >> v >> w;
        --u, --v;
        G[u].pb({v, w, i});
        G[v].pb({u, w, i});
    }

    const int inf = 1e18;

    vector <int> dp(n, inf);

    for ( int i = 0; i < s; i++ ){
        int u; cin >> u;
        dp[--u] = 0;
    }

    vector <ar<int,2>> tree(n - 1);

    vector <vector<int>> up(n, vector <int> (20, rt)), val(n, vector <int> (20, inf));

    vector <int> tin(n), tout(n), d(n);

    int ct = 0;

    auto Dp = [&](auto Dp, int u, int p) -> void{
        for ( auto &[v, w, i]: G[u] ){
            if ( v != p ){
                Dp(Dp, v, u);
                chmin(dp[u], dp[v] + w);
            }
        }
    };

    Dp(Dp, rt, rt);

    auto dfs = [&](auto dfs, int u, int p) -> void{
        tin[u] = ++ct;
        up[u][0] = p;
        val[u][0] = dp[u] - d[u];
        for ( int i = 1; i < 20; i++ ){
            up[u][i] = up[up[u][i - 1]][i - 1];
            val[u][i] = min(val[u][i - 1], val[up[u][i - 1]][i - 1]);
        }
        for ( auto &[v, w, i]: G[u] ){
            if ( v != p ){
                tree[i] = {u, v};
                d[v] = d[u] + w;
                dfs(dfs, v, u);
            }
        } tout[u] = ct;
    };

    dfs(dfs, rt, rt);

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

    while ( q-- ){
        int i, r; cin >> i >> r;
        --i, --r;
        if ( !isAnc(tree[i][1], r) ){
            cout << "escaped\n";
            continue;
        }
        int opt = dp[r], v = tree[i][0], c = d[r];
        for ( int j = 19; j >= 0; j-- ){
            if ( d[up[r][j]] >= d[v] ){
                chmin(opt, val[r][j] + c);
                r = up[r][j];
            }
        }
        if ( opt == inf ){
            cout << "oo\n";
        } else cout << opt << ln;
    }

    cout << '\n';
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 57428 KB Output is correct
2 Correct 201 ms 57428 KB Output is correct
3 Correct 216 ms 57684 KB Output is correct
4 Correct 266 ms 61268 KB Output is correct
5 Correct 223 ms 61176 KB Output is correct
6 Correct 308 ms 64996 KB Output is correct

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -