oj.uz

Submission #589449

# Submission time Handle Problem Language Result Execution time Memory
589449 2022-07-04T17:24:12 Z Duy_e Valley (BOI19_valley) C++14
100 / 100
 342 ms 55564 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;
        h[v] = h[u] + 1; up[0][v] = u; f[v] = f[u] + w;
        for (int j = 1; j < 20; j ++)
            up[j][v] = up[j - 1][up[j - 1][v]];
        dfs(u, v);
        dp[u] = min(dp[u], dp[v] + w);
    }
}

void dfs2(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;
        dpUp[0][v] = dp[u] - f[u];
        for (int j = 1; j < 20; j ++)
            dpUp[j][v] = min(dpUp[j - 1][v], dpUp[j - 1][up[j - 1][v]]);
        dfs2(u, v);
    }    
}

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);
    // #ifndef ONLINE_JUDGE
    //     freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    // #endif
    
    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);
    dfs2(e, e);
    // for (int i = 1; i <= n; i ++)
    //     cout << dp[i] << ' '; cout << '\n';
    int I, R;
    while (q --) {
        cin >> I >> R;
        // u->v -> par[v] = u

        int u = g[I].u, v = g[I].v;
        // cout << v << ' ' << R << ' ' << h[v] << ' ' << h[R] << ' ' << jump(R, h[R] - h[v]) << '\n';
        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:119:9: warning: "/*" within comment [-Wcomment]
  119 | /**  /\_/\
      |          
valley.cpp: In function 'void dfs2(int, int)':
valley.cpp:37:38: warning: unused variable 'w' [-Wunused-variable]
   37 |         int v = g[i].u ^ g[i].v ^ u, w = g[i].w;
      |                                      ^
valley.cpp: In function 'int main()':
valley.cpp:101:13: warning: unused variable 'u' [-Wunused-variable]
  101 |         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 5460 KB Output is correct
2 Correct 5 ms 5456 KB Output is correct
3 Correct 6 ms 5460 KB Output is correct
4 Correct 6 ms 5480 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5460 KB Output is correct
2 Correct 5 ms 5456 KB Output is correct
3 Correct 6 ms 5460 KB Output is correct
4 Correct 6 ms 5480 KB Output is correct
5 Correct 6 ms 5716 KB Output is correct
6 Correct 4 ms 5716 KB Output is correct
7 Correct 4 ms 5680 KB Output is correct
8 Correct 4 ms 5716 KB Output is correct
9 Correct 4 ms 5716 KB Output is correct
10 Correct 4 ms 5684 KB Output is correct
11 Correct 4 ms 5716 KB Output is correct
12 Correct 4 ms 5680 KB Output is correct
13 Correct 4 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 202 ms 50584 KB Output is correct
2 Correct 234 ms 50404 KB Output is correct
3 Correct 236 ms 50260 KB Output is correct
4 Correct 315 ms 52516 KB Output is correct
5 Correct 256 ms 52728 KB Output is correct
6 Correct 342 ms 55144 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5460 KB Output is correct
2 Correct 5 ms 5456 KB Output is correct
3 Correct 6 ms 5460 KB Output is correct
4 Correct 6 ms 5480 KB Output is correct
5 Correct 6 ms 5716 KB Output is correct
6 Correct 4 ms 5716 KB Output is correct
7 Correct 4 ms 5680 KB Output is correct
8 Correct 4 ms 5716 KB Output is correct
9 Correct 4 ms 5716 KB Output is correct
10 Correct 4 ms 5684 KB Output is correct
11 Correct 4 ms 5716 KB Output is correct
12 Correct 4 ms 5680 KB Output is correct
13 Correct 4 ms 5716 KB Output is correct
14 Correct 4 ms 5716 KB Output is correct
15 Correct 202 ms 50584 KB Output is correct
16 Correct 234 ms 50404 KB Output is correct
17 Correct 236 ms 50260 KB Output is correct
18 Correct 315 ms 52516 KB Output is correct
19 Correct 256 ms 52728 KB Output is correct
20 Correct 342 ms 55144 KB Output is correct
21 Correct 180 ms 49264 KB Output is correct
22 Correct 212 ms 49076 KB Output is correct
23 Correct 243 ms 49024 KB Output is correct
24 Correct 255 ms 51504 KB Output is correct
25 Correct 302 ms 54988 KB Output is correct
26 Correct 210 ms 49620 KB Output is correct
27 Correct 217 ms 49316 KB Output is correct
28 Correct 228 ms 49320 KB Output is correct
29 Correct 265 ms 51064 KB Output is correct
30 Correct 320 ms 52896 KB Output is correct
31 Correct 193 ms 50168 KB Output is correct
32 Correct 250 ms 49988 KB Output is correct
33 Correct 221 ms 49952 KB Output is correct
34 Correct 263 ms 52188 KB Output is correct
35 Correct 314 ms 55564 KB Output is correct
36 Correct 263 ms 52012 KB Output is correct