oj.uz

Submission #936305

# Submission time Handle Problem Language Result Execution time Memory
936305 2024-03-01T14:33:55 Z Szil Cyberland (APIO23_cyberland) C++17
100 / 100
 810 ms 64848 KB 
#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;
using ld = double;

const int MAXN = 100'001;
const int MAXK = 67;

struct Q {
    ld d;
    int u, k;

    bool operator<(const Q &x) const {
        if (k == x.k) return d > x.d;
        return k > x.k;
    }
};

vector<pair<int, ld>> g[MAXN];
ld dist[MAXN][MAXK];
bool vis[MAXN];

void dfs(int u, int H) {
    vis[u] = true;
    if (u == H) return;
    for (auto [v, w] : g[u]) {
        if (!vis[v]) dfs(v, H);
    }
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    K = min(K, MAXK-1);

    for (int i = 0; i < N; i++) {
        g[i].clear();
        vis[i] = false;
        for (int j = 0; j <= K; j++) {
            dist[i][j] = 1e18;
        }
    }
    for (int i = 0; i < M; i++) {
        g[x[i]].emplace_back(y[i], c[i]);
        g[y[i]].emplace_back(x[i], c[i]);
    }
    dfs(0, H);
    if (!vis[H]) {
        return -1;
    }
    priority_queue<Q> pq;
    for (int i = 0; i < N; i++) {
        if (vis[i] && (arr[i] == 0 || i == 0)) {
            pq.push({0, i, 0});
            dist[i][0] = 0;
        }
    }
    while (!pq.empty()) {
        auto [d, u, k] = pq.top(); pq.pop();
        if (u == H || d > dist[u][k]) continue;
        for (auto [v, w] : g[u]) {
            if (arr[v] == 0) continue;
            ld cost = dist[u][k] + w;
            if (dist[v][k] > cost) {
                dist[v][k] = cost;
                pq.push({cost, v, k});
            }
            cost /= 2;
            if (arr[v] == 2 && k < K && dist[v][k+1] > cost) {
                dist[v][k+1] = cost;
                pq.push({cost, v, k+1});
            }
        }
    }
    ld ans = 1e18;
    for (int i = 0; i <= K; i++) {
        ans = min(ans, dist[H][i]);
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3932 KB Correct.
2 Correct 16 ms 3928 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6164 KB Correct.
2 Correct 22 ms 5980 KB Correct.
3 Correct 21 ms 5980 KB Correct.
4 Correct 22 ms 6180 KB Correct.
5 Correct 27 ms 5980 KB Correct.
6 Correct 19 ms 10844 KB Correct.
7 Correct 25 ms 10828 KB Correct.
8 Correct 13 ms 15708 KB Correct.
9 Correct 20 ms 3784 KB Correct.
10 Correct 20 ms 3932 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5976 KB Correct.
2 Correct 22 ms 5976 KB Correct.
3 Correct 27 ms 5980 KB Correct.
4 Correct 26 ms 4200 KB Correct.
5 Correct 23 ms 3928 KB Correct.
6 Correct 6 ms 10844 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 39880 KB Correct.
2 Correct 66 ms 5980 KB Correct.
3 Correct 57 ms 6164 KB Correct.
4 Correct 65 ms 6236 KB Correct.
5 Correct 42 ms 3928 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6232 KB Correct.
2 Correct 20 ms 6236 KB Correct.
3 Correct 20 ms 6268 KB Correct.
4 Correct 21 ms 11356 KB Correct.
5 Correct 18 ms 3980 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6248 KB Correct.
2 Correct 19 ms 6232 KB Correct.
3 Correct 41 ms 51420 KB Correct.
4 Correct 15 ms 9052 KB Correct.
5 Correct 20 ms 3980 KB Correct.
6 Correct 22 ms 6236 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 6268 KB Correct.
2 Correct 13 ms 6232 KB Correct.
3 Correct 508 ms 63648 KB Correct.
4 Correct 198 ms 18420 KB Correct.
5 Correct 251 ms 32188 KB Correct.
6 Correct 133 ms 16596 KB Correct.
7 Correct 197 ms 20304 KB Correct.
8 Correct 167 ms 6480 KB Correct.
9 Correct 58 ms 6236 KB Correct.
10 Correct 54 ms 6236 KB Correct.
11 Correct 153 ms 6204 KB Correct.
12 Correct 63 ms 6224 KB Correct.
13 Correct 65 ms 6236 KB Correct.
14 Correct 227 ms 33024 KB Correct.
15 Correct 183 ms 13248 KB Correct.
16 Correct 62 ms 6228 KB Correct.
17 Correct 74 ms 6228 KB Correct.
18 Correct 65 ms 6236 KB Correct.
19 Correct 147 ms 5980 KB Correct.
20 Correct 5 ms 3932 KB Correct.
21 Correct 6 ms 5976 KB Correct.
22 Correct 12 ms 6748 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 6236 KB Correct.
2 Correct 22 ms 6232 KB Correct.
3 Correct 777 ms 64848 KB Correct.
4 Correct 225 ms 8784 KB Correct.
5 Correct 530 ms 32212 KB Correct.
6 Correct 252 ms 16604 KB Correct.
7 Correct 344 ms 26452 KB Correct.
8 Correct 216 ms 6508 KB Correct.
9 Correct 103 ms 6224 KB Correct.
10 Correct 95 ms 6224 KB Correct.
11 Correct 115 ms 4024 KB Correct.
12 Correct 113 ms 6228 KB Correct.
13 Correct 121 ms 6132 KB Correct.
14 Correct 810 ms 30776 KB Correct.
15 Correct 635 ms 37140 KB Correct.
16 Correct 324 ms 18408 KB Correct.
17 Correct 237 ms 8224 KB Correct.
18 Correct 112 ms 7252 KB Correct.
19 Correct 126 ms 7252 KB Correct.
20 Correct 117 ms 7252 KB Correct.
21 Correct 277 ms 8212 KB Correct.
22 Correct 7 ms 3932 KB Correct.
23 Correct 10 ms 5980 KB Correct.
24 Correct 22 ms 6748 KB Correct.