oj.uz

Submission #957520

# Submission time Handle Problem Language Result Execution time Memory
957520 2024-04-04T00:27:25 Z Pring Cyberland (APIO23_cyberland) C++17
97 / 100
 1969 ms 252668 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
using ll = __int128_t;

namespace {
    const int MXN = 100005, MXK = 35;
    int n, m, k, h;
    vector<int> u, v, w, a;
    vector<pdi> edge[MXN * MXK];
    double dis[MXN * MXK];
    vector<int> zero;
    bitset<MXN> b;

    inline int f(int x, int y) {
        return x * n + y;
    }

    void build_graph1() {
        FOR(i, 0, m) {
            int x = u[i], y = v[i];
            double z = w[i];
            if (x != h) edge[x].push_back(mp(z, y));
            if (y != h) edge[y].push_back(mp(z, x));
        }
    }

    void DFS(int id) {
        b[id] = true;
        for (auto &[w, i] : edge[id]) {
            if (b[i]) continue;
            DFS(i);
        }
    }

    void find_zero() {
        zero.clear();
        zero.push_back(1);
        FOR(i, 1, n + 1) b[i] = 0;
        DFS(1);
        FOR(i, 1, n + 1) if (a[i] == 0 && b[i]) zero.push_back(i);
    }

    void cls_graph() {
        FOR(i, 1, n + 1) edge[i].clear();
    }

    void build_graph2() {
        auto PUT = [&](int x, int y, double z) -> void {
            if (a[x] == 2) {
                FOR(i, 0, k) edge[f(i, x)].push_back(mp(z * (2LL << i), f(i + 1, y)));;
            }
            FOR(i, 0, k + 1) edge[f(i, x)].push_back(mp(z * (1LL << i), f(i, y)));
        };
        for (auto &i : zero) edge[0].push_back(mp(0.0, i));
        FOR(i, 0, m) {
            int x = u[i], y = v[i];
            double z = w[i];
            if (x != h) PUT(x, y, z);
            if (y != h) PUT(y, x, z);
        }
    }

    void DIJKSTRA() {
        priority_queue<pdi, vector<pdi>, greater<pdi>> pq;
        fill(dis, dis + n * k + n + 1, 3.9e239);
        pq.push(mp(0.0, 0));
        while (pq.size()) {
            auto [len, id] = pq.top();
            pq.pop();
            if (dis[id] < 3.9e239) continue;
            dis[id] = len;
            for (auto &[w, i] : edge[id]) {
                if (dis[i] < 3.9e239) continue;
                pq.push(mp(len + w, i));
            }
        }
    }

    void RESET() {
        FOR(i, 0, n * (k + 1) + 1) edge[i].clear();
    }

    double APIO() {
        assert(k <= 30);
        build_graph1();
        find_zero();
        cls_graph();
        build_graph2();
        DIJKSTRA();
        double ans = 3.9e239;
        FOR(i, 0, k + 1) {
            ans = min(ans, dis[f(i, h)] / (1LL << i));
        }
        RESET();
        return (ans >= 2e18 ? -1.0 : ans);
    }
}

double solve(int N, int M, int K, int H, vector<int> U, vector<int> V, vector<int> W, vector<int> A) {
    H++;
    for (auto &i : U) i++;
    for (auto &i : V) i++;
    A.insert(A.begin(), 0);
    ::n = N;
    ::m = M;
    ::k = K;
    ::h = H;
    ::u = U;
    ::v = V;
    ::w = W;
    ::a = A;
    return APIO();
}

#ifdef MIKU
void READ(vector<int> &v) {
    int n;
    cin >> n;
    v.resize(n);
    for (auto &i : v) cin >> i;
}

void miku() {
    int n, m, k, h;
    vector<int> u, v, w, a;
    cin >> n >> m >> k >> h;
    READ(u);
    READ(v);
    READ(w);
    READ(a);
    cout << solve(n, m, k, h, u, v, w, a) << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}
#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 83252 KB Correct.
2 Correct 45 ms 83340 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 88208 KB Correct.
2 Correct 82 ms 88580 KB Correct.
3 Correct 77 ms 88324 KB Correct.
4 Correct 95 ms 88512 KB Correct.
5 Correct 83 ms 88400 KB Correct.
6 Correct 156 ms 110948 KB Correct.
7 Correct 178 ms 112996 KB Correct.
8 Correct 179 ms 119888 KB Correct.
9 Correct 68 ms 83800 KB Correct.
10 Correct 68 ms 83800 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 88400 KB Correct.
2 Correct 85 ms 88480 KB Correct.
3 Correct 79 ms 88396 KB Correct.
4 Correct 72 ms 83804 KB Correct.
5 Correct 72 ms 83800 KB Correct.
6 Correct 81 ms 98456 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 204508 KB Correct.
2 Correct 225 ms 86080 KB Correct.
3 Correct 205 ms 86208 KB Correct.
4 Correct 229 ms 86100 KB Correct.
5 Correct 160 ms 83292 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 89024 KB Correct.
2 Correct 87 ms 89544 KB Correct.
3 Correct 81 ms 89340 KB Correct.
4 Correct 199 ms 121672 KB Correct.
5 Correct 62 ms 83804 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 89428 KB Correct.
2 Correct 73 ms 89732 KB Correct.
3 Correct 1091 ms 225540 KB Correct.
4 Correct 150 ms 108120 KB Correct.
5 Correct 68 ms 83852 KB Correct.
6 Correct 76 ms 89936 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 92028 KB Correct.
2 Correct 83 ms 92304 KB Correct.
3 Correct 1075 ms 190692 KB Correct.
4 Correct 537 ms 122204 KB Correct.
5 Correct 1969 ms 252668 KB Correct.
6 Correct 1175 ms 240248 KB Correct.
7 Correct 516 ms 120492 KB Correct.
8 Correct 304 ms 93264 KB Correct.
9 Correct 295 ms 93568 KB Correct.
10 Correct 277 ms 94232 KB Correct.
11 Correct 295 ms 88700 KB Correct.
12 Correct 297 ms 93428 KB Correct.
13 Correct 318 ms 93624 KB Correct.
14 Correct 496 ms 119764 KB Correct.
15 Correct 394 ms 101376 KB Correct.
16 Correct 308 ms 93196 KB Correct.
17 Correct 339 ms 93624 KB Correct.
18 Correct 328 ms 93152 KB Correct.
19 Correct 644 ms 93588 KB Correct.
20 Correct 38 ms 84008 KB Correct.
21 Correct 43 ms 86392 KB Correct.
22 Correct 131 ms 101664 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 93 ms 168212 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -