oj.uz

Submission #589458

# Submission time Handle Problem Language Result Execution time Memory
589458 2022-07-04T17:44:02 Z Duy_e Valley (BOI19_valley) C++14
100 / 100
 209 ms 52264 KB 
/*
**  TASK: 
**  LINK: 
*/
 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long INF = 1e18;
const long long N = 2e5 + 5;
 
struct edge {
    ll u, v, w, id;
} g[N];
 
ll n, s, q, e, shop[N], up[20][N], h[N], dpUp[20][N], f[N], dp[N];
vector <int> d[N];
 
void dfs(int p, int u) {
    for (int i: d[u]) {
        int v = g[i].u ^ g[i].v ^ u, w = g[i].w;
        if (v == p) continue;
        g[i].u = u; g[i].v = v;
        h[v] = h[u] + 1; up[0][v] = u; f[v] = f[u] + w;
        dfs(u, v);
        dp[u] = min(dp[u], dp[v] + w);
    }

    for (int i: d[u]) { int v = g[i].u ^ g[i].v ^ u, w = g[i].w;
        if (v == p) continue;
        dpUp[0][v] = dp[u] - f[u];
    }

}
 
int jump(int u, int k) {
    for (int i = 19; i >= 0; i --) if ((k >> i) & 1) u = up[i][u];
    return u;
}
 
bool isANC(int p, int u) {
    int delta = h[u] - h[p];
    return jump(u, delta) == p;
}
 
ll get(int u, int k) {
    ll ans = INF;
    for (int i = 19; i >= 0; i --) if ((k >> i) & 1) {
        ans = min(ans, dpUp[i][u]);
        u = up[i][u];
    }
    return ans;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i ++) {
        cin >> g[i].u >> g[i].v >> g[i].w;
        g[i].id = i;
        d[g[i].u].push_back(i);
        d[g[i].v].push_back(i);
    }
 
    for (int i = 0; i < 20; i ++)
        for (int j = 1; j <= n; j ++)
            dpUp[i][j] = INF;
 
    for (int i = 1, x; i <= s; i ++) 
        cin >> x, shop[x] = true;
 
    for (int i = 1; i <= n; i ++)
        if (shop[i]) dp[i] = 0; else dp[i] = INF;
 
    // "e" is root
    dfs(e, e);
 
    for (int i = 1; i < 20; i ++)
        for (int j = 1; j <= n; j ++) {
            up[i][j] = up[i - 1][up[i - 1][j]];
            dpUp[i][j] = min(dpUp[i - 1][j], dpUp[i - 1][up[i - 1][j]]);
        }

    int I, R;
    while (q --) {
        cin >> I >> R;
        
        int u = g[I].u, v = g[I].v;
        if (!isANC(v, R)) {
            cout << "escaped\n";
            continue;
        }
 
        if (dp[v] == INF) {
            cout << "oo\n";
            continue;
        }
 
        cout << min(f[R] + get(R, h[R] - h[v]), dp[R]) << '\n';
 
    }
 
    return 0;
}    
/**  /\_/\
*   (= ._.)
*   / >🍵 \>🍮
**/

Compilation message

valley.cpp:111:9: warning: "/*" within comment [-Wcomment]
  111 | /**  /\_/\
      |          
valley.cpp: In function 'void dfs(int, int)':
valley.cpp:33:54: warning: unused variable 'w' [-Wunused-variable]
   33 |     for (int i: d[u]) { int v = g[i].u ^ g[i].v ^ u, w = g[i].w;
      |                                                      ^
valley.cpp: In function 'int main()':
valley.cpp:94:13: warning: unused variable 'u' [-Wunused-variable]
   94 |         int u = g[I].u, v = g[I].v;
      |             ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5332 KB Output is correct
2 Correct 6 ms 5468 KB Output is correct
3 Correct 5 ms 5388 KB Output is correct
4 Correct 6 ms 5460 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5332 KB Output is correct
2 Correct 6 ms 5468 KB Output is correct
3 Correct 5 ms 5388 KB Output is correct
4 Correct 6 ms 5460 KB Output is correct
5 Correct 4 ms 5716 KB Output is correct
6 Correct 4 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 3 ms 5696 KB Output is correct
9 Correct 3 ms 5716 KB Output is correct
10 Correct 3 ms 5716 KB Output is correct
11 Correct 3 ms 5716 KB Output is correct
12 Correct 3 ms 5716 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 4 ms 5716 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 46768 KB Output is correct
2 Correct 156 ms 46528 KB Output is correct
3 Correct 144 ms 46436 KB Output is correct
4 Correct 174 ms 48696 KB Output is correct
5 Correct 181 ms 48796 KB Output is correct
6 Correct 209 ms 51344 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5332 KB Output is correct
2 Correct 6 ms 5468 KB Output is correct
3 Correct 5 ms 5388 KB Output is correct
4 Correct 6 ms 5460 KB Output is correct
5 Correct 4 ms 5716 KB Output is correct
6 Correct 4 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 3 ms 5696 KB Output is correct
9 Correct 3 ms 5716 KB Output is correct
10 Correct 3 ms 5716 KB Output is correct
11 Correct 3 ms 5716 KB Output is correct
12 Correct 3 ms 5716 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 4 ms 5716 KB Output is correct
15 Correct 144 ms 46768 KB Output is correct
16 Correct 156 ms 46528 KB Output is correct
17 Correct 144 ms 46436 KB Output is correct
18 Correct 174 ms 48696 KB Output is correct
19 Correct 181 ms 48796 KB Output is correct
20 Correct 209 ms 51344 KB Output is correct
21 Correct 113 ms 46168 KB Output is correct
22 Correct 165 ms 45828 KB Output is correct
23 Correct 140 ms 45768 KB Output is correct
24 Correct 152 ms 48192 KB Output is correct
25 Correct 188 ms 51696 KB Output is correct
26 Correct 109 ms 46384 KB Output is correct
27 Correct 126 ms 46032 KB Output is correct
28 Correct 176 ms 46164 KB Output is correct
29 Correct 158 ms 47712 KB Output is correct
30 Correct 197 ms 49612 KB Output is correct
31 Correct 114 ms 46908 KB Output is correct
32 Correct 150 ms 46560 KB Output is correct
33 Correct 176 ms 46632 KB Output is correct
34 Correct 175 ms 48864 KB Output is correct
35 Correct 188 ms 52264 KB Output is correct
36 Correct 169 ms 49112 KB Output is correct