oj.uz

Submission #781987

# Submission time Handle Problem Language Result Execution time Memory
781987 2023-07-13T14:32:59 Z t6twotwo Cyberland (APIO23_cyberland) C++17
100 / 100
 2640 ms 12212 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr double inf = 1E18;
double solve(int N, int M, int K, int H, std::vector<int> U, std::vector<int> V, std::vector<int> W, std::vector<int> a) {
    K = min(K, 70);
    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[U[i]].emplace_back(V[i], W[i]);
        adj[V[i]].emplace_back(U[i], W[i]);
    }
    vector<bool> vis(N);
    vis[0] = 1;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (x == H) {
            continue;
        }
        for (auto [y, z] : adj[x]) {
            if (!vis[y]) {
                vis[y] = 1;
                q.push(y);
            }
        }
    }
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
    pq.emplace(0, 0);
    for (int i = 0; i < N; i++) {
        if (a[i] == 0 && vis[i]) {
            pq.emplace(0, i);
        }
    }
    double ans = inf;
    for (int i = K; i >= 0; i--) {
        priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> h;
        vector<bool> f(N);
        while (!pq.empty()) {
            auto [s, x] = pq.top();
            pq.pop();
            if (f[x]) {
                continue;
            }
            f[x] = 1;
            if (x == H) {
                ans = min(ans, s);
                continue;
            }
            for (auto [y, z] : adj[x]) {
                pq.emplace(s + z, y);
                if (a[y] == 2) {
                    h.emplace((s + z) / 2, y);
                }
            }
        }
        swap(h, pq);
    }
    if (ans == inf) {
        return -1;
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 468 KB Correct.
2 Correct 25 ms 716 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 800 KB Correct.
2 Correct 28 ms 1276 KB Correct.
3 Correct 27 ms 1260 KB Correct.
4 Correct 32 ms 1228 KB Correct.
5 Correct 27 ms 1276 KB Correct.
6 Correct 23 ms 2080 KB Correct.
7 Correct 31 ms 2080 KB Correct.
8 Correct 14 ms 2588 KB Correct.
9 Correct 26 ms 1120 KB Correct.
10 Correct 25 ms 1096 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1324 KB Correct.
2 Correct 30 ms 1292 KB Correct.
3 Correct 28 ms 1296 KB Correct.
4 Correct 28 ms 624 KB Correct.
5 Correct 31 ms 1108 KB Correct.
6 Correct 6 ms 1620 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 6912 KB Correct.
2 Correct 192 ms 1300 KB Correct.
3 Correct 165 ms 1344 KB Correct.
4 Correct 182 ms 1488 KB Correct.
5 Correct 86 ms 1096 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1276 KB Correct.
2 Correct 30 ms 1252 KB Correct.
3 Correct 28 ms 1364 KB Correct.
4 Correct 26 ms 2004 KB Correct.
5 Correct 24 ms 1076 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1228 KB Correct.
2 Correct 24 ms 1160 KB Correct.
3 Correct 32 ms 8624 KB Correct.
4 Correct 17 ms 1848 KB Correct.
5 Correct 26 ms 1224 KB Correct.
6 Correct 26 ms 1044 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 1324 KB Correct.
2 Correct 54 ms 724 KB Correct.
3 Correct 503 ms 11564 KB Correct.
4 Correct 383 ms 4452 KB Correct.
5 Correct 1099 ms 10908 KB Correct.
6 Correct 1016 ms 12212 KB Correct.
7 Correct 396 ms 3680 KB Correct.
8 Correct 307 ms 2376 KB Correct.
9 Correct 280 ms 1356 KB Correct.
10 Correct 278 ms 1308 KB Correct.
11 Correct 276 ms 2368 KB Correct.
12 Correct 280 ms 1144 KB Correct.
13 Correct 304 ms 1324 KB Correct.
14 Correct 369 ms 6360 KB Correct.
15 Correct 359 ms 3344 KB Correct.
16 Correct 296 ms 1276 KB Correct.
17 Correct 322 ms 1484 KB Correct.
18 Correct 323 ms 1348 KB Correct.
19 Correct 637 ms 2324 KB Correct.
20 Correct 12 ms 340 KB Correct.
21 Correct 20 ms 468 KB Correct.
22 Correct 91 ms 1680 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 750 ms 1180 KB Correct.
2 Correct 121 ms 596 KB Correct.
3 Correct 171 ms 11312 KB Correct.
4 Correct 448 ms 3148 KB Correct.
5 Correct 2640 ms 11180 KB Correct.
6 Correct 2397 ms 11792 KB Correct.
7 Correct 771 ms 5336 KB Correct.
8 Correct 393 ms 2004 KB Correct.
9 Correct 615 ms 1360 KB Correct.
10 Correct 577 ms 1320 KB Correct.
11 Correct 210 ms 1532 KB Correct.
12 Correct 609 ms 1568 KB Correct.
13 Correct 669 ms 1468 KB Correct.
14 Correct 2202 ms 7656 KB Correct.
15 Correct 1270 ms 5860 KB Correct.
16 Correct 655 ms 2896 KB Correct.
17 Correct 453 ms 1556 KB Correct.
18 Correct 654 ms 1044 KB Correct.
19 Correct 706 ms 696 KB Correct.
20 Correct 712 ms 796 KB Correct.
21 Correct 1409 ms 448 KB Correct.
22 Correct 19 ms 340 KB Correct.
23 Correct 40 ms 340 KB Correct.
24 Correct 220 ms 1496 KB Correct.