oj.uz

Submission #809142

# Submission time Handle Problem Language Result Execution time Memory
809142 2023-08-05T18:56:30 Z PanosPask Valley (BOI19_valley) C++14
100 / 100
 137 ms 55264 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back

using namespace std;

const int MAXLOG = 17;

typedef long long ll;
typedef pair<int, int> pi;

const ll INF = 1e18;

struct Node {
    ll dist;
    ll val;
    int anc;
};

int N, S, Q, E;
vector<ll> shopdist;
vector<bool> isshop;
vector<Node> ancestor[MAXLOG];
vector<vector<pi>> adj_list;
vector<int> tin;
vector<int> tout;
vector<int> dep;
vector<pi> edges;
int counter;

void dfs(int node, int par)
{
    tin[node] = counter++;
    if (par != -1)
        dep[node] = dep[par] + 1;
    else
        dep[node] = 0;

    shopdist[node] = INF;
    if (isshop[node])
        shopdist[node] = 0;

    for (auto [neigh, w] : adj_list[node]) {
        if (neigh == par) {
            ancestor[0][node].dist = w;
            continue;
        }

        dfs(neigh, node);
        shopdist[node] = min(shopdist[node], shopdist[neigh] + w);
    }

    ancestor[0][node].val = shopdist[node];
    ancestor[0][node].anc = par;

    tout[node] = counter;
}

void calculate_ancestors(void)
{
    for (int up = 1; up < MAXLOG; up++) {
        ancestor[up].resize(N + 1);
        for (int i = 0; i < N; i++) {
            int u = ancestor[up - 1][i].anc;

            ancestor[up][i].anc = ancestor[up - 1][u].anc;
            ancestor[up][i].dist = ancestor[up - 1][i].dist + ancestor[up - 1][u].dist;
            ancestor[up][i].val = min(ancestor[up - 1][i].val, ancestor[up - 1][i].dist + ancestor[up - 1][u].val);
        }
    }
}

ll jump(int v, int lvl)
{
    ll ans = INF;
    ll dist = 0;
    for (int up = 0; up < MAXLOG; up++) {
        if (((1 << up) & lvl) == 0)
            continue;

        ans = min(ans, ancestor[up][v].val + dist);
        dist = dist + ancestor[up][v].dist;
        v = ancestor[up][v].anc;
    }

    return ans;
}

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

int main(void)
{
    scanf("%d %d %d %d", &N, &S, &Q, &E);
    E--;

    shopdist.resize(N);
    isshop.assign(N, false);
    adj_list.resize(N);
    tin.resize(N);
    tout.resize(N);
    dep.resize(N);

    ancestor[0].resize(N + 1);

    for (int i = 0; i < N - 1; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        u--; v--;

        adj_list[u].pb(mp(v, w));
        adj_list[v].pb(mp(u, w));
        edges.pb(mp(u, v));
    }

    for (int i = 0; i < S; i++) {
        int v;
        scanf("%d", &v);

        isshop[v - 1] = true;
    }

    dfs(E, -1);
    ancestor[0][E].anc = N;
    ancestor[0][N].anc = N;

    calculate_ancestors();

    for (int q = 0; q < Q; q++) {
        int I, R;
        scanf("%d %d", &I, &R);
        I--; R--;

        if (dep[edges[I].f] > dep[edges[I].s])
            swap(edges[I].f, edges[I].s);

        if (!is_ancestor(edges[I].s, R)) {
            printf("escaped\n");
        }
        else {
            ll v = jump(R, dep[R] - dep[edges[I].f]);
            if (v == INF)
                printf("oo\n");
            else
                printf("%lld\n", v);
        }
    }
}

Compilation message

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:45:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for (auto [neigh, w] : adj_list[node]) {
      |               ^
valley.cpp: In function 'int main()':
valley.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     scanf("%d %d %d %d", &N, &S, &Q, &E);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         scanf("%d %d %d", &u, &v, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf("%d", &v);
      |         ~~~~~^~~~~~~~~~
valley.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         scanf("%d %d", &I, &R);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 49836 KB Output is correct
2 Correct 101 ms 49532 KB Output is correct
3 Correct 99 ms 49472 KB Output is correct
4 Correct 137 ms 51576 KB Output is correct
5 Correct 105 ms 51648 KB Output is correct
6 Correct 118 ms 53992 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 94 ms 49836 KB Output is correct
16 Correct 101 ms 49532 KB Output is correct
17 Correct 99 ms 49472 KB Output is correct
18 Correct 137 ms 51576 KB Output is correct
19 Correct 105 ms 51648 KB Output is correct
20 Correct 118 ms 53992 KB Output is correct
21 Correct 93 ms 49916 KB Output is correct
22 Correct 88 ms 49608 KB Output is correct
23 Correct 90 ms 49544 KB Output is correct
24 Correct 110 ms 52032 KB Output is correct
25 Correct 105 ms 55264 KB Output is correct
26 Correct 82 ms 49856 KB Output is correct
27 Correct 87 ms 49624 KB Output is correct
28 Correct 92 ms 49484 KB Output is correct
29 Correct 105 ms 51104 KB Output is correct
30 Correct 112 ms 52912 KB Output is correct
31 Correct 84 ms 49980 KB Output is correct
32 Correct 97 ms 49636 KB Output is correct
33 Correct 113 ms 49580 KB Output is correct
34 Correct 111 ms 51808 KB Output is correct
35 Correct 118 ms 55036 KB Output is correct
36 Correct 104 ms 52424 KB Output is correct