oj.uz

Submission #379969

# Submission time Handle Problem Language Result Execution time Memory
379969 2021-03-19T20:56:03 Z couplefire Valley (BOI19_valley) C++17
100 / 100
 563 ms 59116 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define INF 10000000000000000ll

int n, s, q, r;
vector<pair<int, long long>> adj[MAXN];
pair<int, int> edges[MAXN];
int tin[MAXN], tout[MAXN];
long long sumDepth[MAXN];
int depth[MAXN];
int curtime = 0;
int up[MAXN][32];
long long minUp[MAXN][32];
long long dp[MAXN];
bool isShop[MAXN];

void dfs(int v, int p = -1, long long d = 0, int dd = 0){
    sumDepth[v] = d;
    depth[v] = dd;
    tin[v] = ++curtime;
    dp[v] = INF;
    up[v][0] = p;
    for(int i = 1; i<32 && up[v][i-1] != -1; i++) up[v][i] = up[up[v][i-1]][i-1];
    for(auto u : adj[v]){
        if(u.first == p) continue;
        dfs(u.first, v, d+u.second, dd+1);
        dp[v] = min(dp[v], dp[u.first]+u.second);
    }
    if(isShop[v]) dp[v] = 0;
    tout[v] = ++curtime;
}

void getMinUp(int v, int p = -1){
    if(p == -1) minUp[v][0] = INF;
    else minUp[v][0] = dp[p]-sumDepth[p];
    for(int i = 1; i<32 && up[v][i-1] != -1; i++) minUp[v][i] = min(minUp[v][i-1], minUp[up[v][i-1]][i-1]);
    for(auto u : adj[v]){
        if(u.first == p) continue;
        getMinUp(u.first, v);
    }
}

bool isPar(int a, int b){
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

long long query(int v, int h){
    long long ans = INF;
    for(int i = 30; i>=0; i--){
        if((1<<i) <= h){
            ans = min(ans, minUp[v][i]);
            // cout << (1<<i) << endl;
            v = up[v][i];
            h -= (1<<i);
        }
    }
    return ans;
}

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s >> q >> r;
    --r;
    for(int i = 0; i<n-1; i++){
        int a, b; cin >> a >> b;
        --a; --b;
        int w; cin >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
        edges[i] = {a, b};
    }
    for(int i = 0; i<s; i++){
        int a; cin >> a; --a;
        isShop[a] = 1;
    }
    dfs(r);
    getMinUp(r);
    while(q--){
        int ind, v; cin >> ind >> v;
        --ind; --v;
        int a = edges[ind].first, b = edges[ind].second;
        if(depth[a] < depth[b]) swap(a, b);
        if(!(isPar(a, v) && isPar(b, v))){
            cout << "escaped" << endl;
            continue;
        }
        // cout << query(v, depth[v]-depth[a]) << endl;
        long long ans = sumDepth[v]+min(dp[v]-sumDepth[v], query(v, depth[v]-depth[a]));
        if(ans >= INF/2) cout << "oo" << endl;
        else cout << ans << endl;
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2924 KB Output is correct
2 Correct 26 ms 2924 KB Output is correct
3 Correct 26 ms 2924 KB Output is correct
4 Correct 26 ms 2924 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2924 KB Output is correct
2 Correct 26 ms 2924 KB Output is correct
3 Correct 26 ms 2924 KB Output is correct
4 Correct 26 ms 2924 KB Output is correct
5 Correct 5 ms 3308 KB Output is correct
6 Correct 5 ms 3308 KB Output is correct
7 Correct 6 ms 3328 KB Output is correct
8 Correct 7 ms 3308 KB Output is correct
9 Correct 6 ms 3308 KB Output is correct
10 Correct 7 ms 3308 KB Output is correct
11 Correct 5 ms 3308 KB Output is correct
12 Correct 6 ms 3308 KB Output is correct
13 Correct 6 ms 3308 KB Output is correct
14 Correct 6 ms 3308 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 53484 KB Output is correct
2 Correct 449 ms 53356 KB Output is correct
3 Correct 464 ms 53740 KB Output is correct
4 Correct 517 ms 55868 KB Output is correct
5 Correct 476 ms 56172 KB Output is correct
6 Correct 563 ms 58476 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2924 KB Output is correct
2 Correct 26 ms 2924 KB Output is correct
3 Correct 26 ms 2924 KB Output is correct
4 Correct 26 ms 2924 KB Output is correct
5 Correct 5 ms 3308 KB Output is correct
6 Correct 5 ms 3308 KB Output is correct
7 Correct 6 ms 3328 KB Output is correct
8 Correct 7 ms 3308 KB Output is correct
9 Correct 6 ms 3308 KB Output is correct
10 Correct 7 ms 3308 KB Output is correct
11 Correct 5 ms 3308 KB Output is correct
12 Correct 6 ms 3308 KB Output is correct
13 Correct 6 ms 3308 KB Output is correct
14 Correct 6 ms 3308 KB Output is correct
15 Correct 433 ms 53484 KB Output is correct
16 Correct 449 ms 53356 KB Output is correct
17 Correct 464 ms 53740 KB Output is correct
18 Correct 517 ms 55868 KB Output is correct
19 Correct 476 ms 56172 KB Output is correct
20 Correct 563 ms 58476 KB Output is correct
21 Correct 415 ms 53356 KB Output is correct
22 Correct 435 ms 52716 KB Output is correct
23 Correct 455 ms 52972 KB Output is correct
24 Correct 489 ms 55532 KB Output is correct
25 Correct 526 ms 59116 KB Output is correct
26 Correct 423 ms 53100 KB Output is correct
27 Correct 424 ms 52844 KB Output is correct
28 Correct 458 ms 53220 KB Output is correct
29 Correct 486 ms 54852 KB Output is correct
30 Correct 551 ms 56684 KB Output is correct
31 Correct 426 ms 53180 KB Output is correct
32 Correct 436 ms 53104 KB Output is correct
33 Correct 480 ms 53228 KB Output is correct
34 Correct 504 ms 55532 KB Output is correct
35 Correct 544 ms 58988 KB Output is correct
36 Correct 498 ms 55532 KB Output is correct