oj.uz

Submission #874620

# Submission time Handle Problem Language Result Execution time Memory
874620 2023-11-17T12:02:43 Z Stickfish Cyberland (APIO23_cyberland) C++17
100 / 100
 2782 ms 13952 KB 
#include "cyberland.h"
#include <cmath>
#include <vector>
#include <cassert>
#include <algorithm>
#include <set>
#include <bitset>
using namespace std;

const int MAXN = 1e5 + 123;
const double INF = 1e18 + 177013;
vector<pair<int, int>> edg[MAXN];
bitset<MAXN> used;

void dfs_connect(int v, int H) {
    if (used[v])
        return;
    used[v] = 1;
    if (v == H)
        return;
    for (auto [u, d] : edg[v]) {
        dfs_connect(u, H);
    }
}

void initialize(int N, int M, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    for (int i = 0; i < N; ++i) {
        edg[i].clear();
    }
    used = 0;
    for (int i = 0; i < M; ++i) {
        edg[x[i]].push_back({y[i], c[i]});
        edg[y[i]].push_back({x[i], c[i]});
    }
}

vector<double> bfs(int N, const vector<pair<double, int>>& inits, double mod) {
    vector<double> depth(N, INF);
    set<pair<double, int>> rdepth;
    used = 0;
    for (const auto &[d, v] : inits) {
        depth[v] = d;
        rdepth.insert({d, v});
    }
    while (rdepth.size()) {
        const auto [d, v] = *rdepth.begin();
        rdepth.erase(rdepth.begin());
        for (auto [u, len] : edg[v]) {
            if (d + len * mod < depth[u]) {
                rdepth.erase({depth[u], u});
                depth[u] = d + len * mod;
                rdepth.insert({depth[u], u});
            }
        }
    }
    return depth;
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    initialize(N, M, x, y, c, arr);
    dfs_connect(0, H);
    if (!used[H])
        return -1;
    double __end_mod = 1;
    if (arr[H] == 0)
        return 0;
    if (arr[H] == 2 && K > 0) {
        arr[H] = 1;
        --K;
        __end_mod = 0.5;
    }

    bitset<MAXN> start;
    for (int i = 0; i < N; ++i) {
        start[i] = used[i] & (i == 0 || arr[i] == 0);
    }
    bitset<MAXN> div2;
    for (int i = 0; i < N; ++i) {
        div2[i] = arr[i] == 2 && used[i];
    }
    K = min({K, 120});
    vector<double> depth;
    double ans = INF;
    depth = bfs(N, {{0, H}}, 1);
    for (int i = start._Find_first(); i < N; i = start._Find_next(i))
        ans = min(ans, depth[i]);

    for (auto [u, d] : edg[H]) {
        edg[u].erase(find(edg[u].begin(), edg[u].end(), pair<int, int>(H, d)));
    }

    for (int ki = 1; ki <= K; ++ki) {
        vector<pair<double, int>> pts;
        for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) {
            pts.push_back({depth[i], i});
        }
        double mod = pow(0.5, ki);
        depth = bfs(N, pts, mod);
        for (int i = start._Find_first(); i < N; i = start._Find_next(i))
            ans = min(ans, depth[i]);
        vector<double> ndepth(N, INF);
        for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) {
            for (auto [u, d] : edg[i])
                ndepth[i] = min(ndepth[i], depth[u] + d * mod);
        }
        for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) {
            depth[i] = ndepth[i];
        }
    }
    return ans * __end_mod;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 3656 KB Correct.
2 Correct 589 ms 2984 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3164 KB Correct.
2 Correct 36 ms 2976 KB Correct.
3 Correct 32 ms 2904 KB Correct.
4 Correct 33 ms 2908 KB Correct.
5 Correct 33 ms 3156 KB Correct.
6 Correct 22 ms 3676 KB Correct.
7 Correct 28 ms 3672 KB Correct.
8 Correct 13 ms 4544 KB Correct.
9 Correct 112 ms 2924 KB Correct.
10 Correct 109 ms 2908 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2904 KB Correct.
2 Correct 44 ms 2904 KB Correct.
3 Correct 39 ms 2956 KB Correct.
4 Correct 115 ms 2904 KB Correct.
5 Correct 124 ms 3168 KB Correct.
6 Correct 7 ms 3416 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 8176 KB Correct.
2 Correct 108 ms 3220 KB Correct.
3 Correct 93 ms 3020 KB Correct.
4 Correct 98 ms 2948 KB Correct.
5 Correct 151 ms 2920 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2988 KB Correct.
2 Correct 30 ms 2908 KB Correct.
3 Correct 25 ms 2904 KB Correct.
4 Correct 25 ms 3752 KB Correct.
5 Correct 63 ms 3160 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2904 KB Correct.
2 Correct 24 ms 2908 KB Correct.
3 Correct 30 ms 9140 KB Correct.
4 Correct 15 ms 3676 KB Correct.
5 Correct 69 ms 2908 KB Correct.
6 Correct 26 ms 3088 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 3016 KB Correct.
2 Correct 28 ms 2904 KB Correct.
3 Correct 403 ms 11408 KB Correct.
4 Correct 270 ms 4944 KB Correct.
5 Correct 708 ms 9944 KB Correct.
6 Correct 313 ms 7568 KB Correct.
7 Correct 287 ms 5016 KB Correct.
8 Correct 237 ms 3152 KB Correct.
9 Correct 143 ms 2984 KB Correct.
10 Correct 120 ms 3028 KB Correct.
11 Correct 221 ms 3172 KB Correct.
12 Correct 162 ms 3268 KB Correct.
13 Correct 155 ms 2904 KB Correct.
14 Correct 263 ms 7056 KB Correct.
15 Correct 272 ms 4176 KB Correct.
16 Correct 144 ms 2940 KB Correct.
17 Correct 174 ms 3060 KB Correct.
18 Correct 152 ms 3008 KB Correct.
19 Correct 411 ms 2904 KB Correct.
20 Correct 12 ms 2652 KB Correct.
21 Correct 11 ms 2908 KB Correct.
22 Correct 22 ms 3164 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 3208 KB Correct.
2 Correct 81 ms 3016 KB Correct.
3 Correct 508 ms 13952 KB Correct.
4 Correct 397 ms 3408 KB Correct.
5 Correct 1769 ms 9956 KB Correct.
6 Correct 675 ms 7656 KB Correct.
7 Correct 669 ms 6652 KB Correct.
8 Correct 430 ms 2960 KB Correct.
9 Correct 362 ms 3412 KB Correct.
10 Correct 324 ms 2980 KB Correct.
11 Correct 2782 ms 3280 KB Correct.
12 Correct 432 ms 4096 KB Correct.
13 Correct 434 ms 4256 KB Correct.
14 Correct 1370 ms 9968 KB Correct.
15 Correct 1366 ms 9372 KB Correct.
16 Correct 495 ms 6584 KB Correct.
17 Correct 443 ms 5624 KB Correct.
18 Correct 368 ms 4056 KB Correct.
19 Correct 475 ms 4200 KB Correct.
20 Correct 402 ms 4096 KB Correct.
21 Correct 1247 ms 5080 KB Correct.
22 Correct 39 ms 3104 KB Correct.
23 Correct 28 ms 2908 KB Correct.
24 Correct 47 ms 3420 KB Correct.