oj.uz

답안 #558625

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558625 2022-05-07T16:18:17 Z Sorting Valley (BOI19_valley) C++17
100 / 100
 264 ms 51720 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

const ll INF = 1e18;
const ll N = 1e5 + 3;
const ll MX = 1e15;
const int LOGN = 20;

int n, s, q, e;
vector<pair<int, ll>> adj[N];
bool shop[N];

int d[N], par[N];
ll up[LOGN][N], min_up[LOGN][N], mdist[N];
ll droot[N];

int lca(int u, int v){
    if(d[u] != d[v]){
        if(d[u] < d[v])
            swap(u, v);

        int diff = d[u] - d[v];
        for(int i = LOGN - 1; i >= 0; --i){
            if(diff >> i & 1){
                u = par[up[i][u]];
            }
        }
    }

    if(u == v)
        return u;

    for(int i = LOGN - 1; i >= 0; --i){
        if(par[up[i][u]] != par[up[i][v]]){
            u = par[up[i][u]];
            v = par[up[i][v]];
        }
    }

    return par[u];
}

void init_up(){
    for(int i = 1; i <= n; ++i){
        up[0][i] = i;
        min_up[0][i] = mdist[i] - droot[i];
    }

    for(int j = 1; j < LOGN; ++j){
        for(int i = 1; i <= n; ++i){
            up[j][i] = up[j - 1][par[up[j - 1][i]]];
            min_up[j][i] = min(min_up[j  - 1][i], min_up[j - 1][par[up[j - 1][i]]]);
        }
    }
}

void dfs(int u, int p){
    par[u] = p;

    mdist[u] = shop[u] ? 0 : INF;
    for(auto [to, w]: adj[u]){
        if(to == p)
            continue;

        d[to] = d[u] + 1;
        droot[to] = droot[u] + w;
        dfs(to, u);
        check_min(mdist[u], mdist[to] + w);
    }
}

array<int, 3> edges[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> s >> q >> e;
    for(int i = 0; i < n - 1; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});

        edges[i + 1] = {u, v, w};
    }

    for(int i = 0; i < s; ++i){
        int c;
        cin >> c;
        shop[c] = true;
    }

    dfs(e, e);
    init_up();

    for(int i = 1; i <= n - 1; ++i){
        if(d[edges[i][0]] < d[edges[i][1]])
            swap(edges[i][0], edges[i][1]);
    }

    for(int i = 0; i < q; ++i){
        int idx, r;
        cin >> idx >> r;

        if(lca(edges[idx][0], r) != edges[idx][0]){
            cout << "escaped\n";
            continue; 
        }

        ll ans = INF;
        int target_d = d[edges[idx][0]];
        int curr_d = d[r];
        
        int num_nodes = curr_d - target_d + 1;
        int cd = r;
        for(int i = LOGN - 1; i >= 0; --i)
            if(num_nodes >> i & 1){
                check_min(ans, droot[r] + min_up[i][cd]);
                cd = par[up[i][cd]];
            }

        if(ans >= MX){
            cout << "oo\n";
        }
        else{
            cout << ans << "\n";
        }
    }
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3028 KB Output is correct
2 Correct 6 ms 3028 KB Output is correct
3 Correct 7 ms 3036 KB Output is correct
4 Correct 5 ms 3028 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3028 KB Output is correct
2 Correct 6 ms 3028 KB Output is correct
3 Correct 7 ms 3036 KB Output is correct
4 Correct 5 ms 3028 KB Output is correct
5 Correct 2 ms 3284 KB Output is correct
6 Correct 2 ms 3284 KB Output is correct
7 Correct 2 ms 3284 KB Output is correct
8 Correct 2 ms 3284 KB Output is correct
9 Correct 2 ms 3284 KB Output is correct
10 Correct 2 ms 3284 KB Output is correct
11 Correct 2 ms 3284 KB Output is correct
12 Correct 3 ms 3284 KB Output is correct
13 Correct 2 ms 3284 KB Output is correct
14 Correct 2 ms 3284 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 46436 KB Output is correct
2 Correct 157 ms 47052 KB Output is correct
3 Correct 186 ms 47160 KB Output is correct
4 Correct 238 ms 49144 KB Output is correct
5 Correct 233 ms 49208 KB Output is correct
6 Correct 264 ms 51336 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3028 KB Output is correct
2 Correct 6 ms 3028 KB Output is correct
3 Correct 7 ms 3036 KB Output is correct
4 Correct 5 ms 3028 KB Output is correct
5 Correct 2 ms 3284 KB Output is correct
6 Correct 2 ms 3284 KB Output is correct
7 Correct 2 ms 3284 KB Output is correct
8 Correct 2 ms 3284 KB Output is correct
9 Correct 2 ms 3284 KB Output is correct
10 Correct 2 ms 3284 KB Output is correct
11 Correct 2 ms 3284 KB Output is correct
12 Correct 3 ms 3284 KB Output is correct
13 Correct 2 ms 3284 KB Output is correct
14 Correct 2 ms 3284 KB Output is correct
15 Correct 182 ms 46436 KB Output is correct
16 Correct 157 ms 47052 KB Output is correct
17 Correct 186 ms 47160 KB Output is correct
18 Correct 238 ms 49144 KB Output is correct
19 Correct 233 ms 49208 KB Output is correct
20 Correct 264 ms 51336 KB Output is correct
21 Correct 136 ms 46536 KB Output is correct
22 Correct 197 ms 46344 KB Output is correct
23 Correct 188 ms 46692 KB Output is correct
24 Correct 206 ms 48856 KB Output is correct
25 Correct 254 ms 51664 KB Output is correct
26 Correct 142 ms 46648 KB Output is correct
27 Correct 181 ms 46440 KB Output is correct
28 Correct 164 ms 46636 KB Output is correct
29 Correct 228 ms 48164 KB Output is correct
30 Correct 233 ms 49916 KB Output is correct
31 Correct 170 ms 46704 KB Output is correct
32 Correct 181 ms 46636 KB Output is correct
33 Correct 169 ms 46836 KB Output is correct
34 Correct 236 ms 48696 KB Output is correct
35 Correct 237 ms 51720 KB Output is correct
36 Correct 218 ms 48780 KB Output is correct