oj.uz

Submission #900610

# Submission time Handle Problem Language Result Execution time Memory
900610 2024-01-08T15:59:11 Z Trisanu_Das Cyberland (APIO23_cyberland) C++17
100 / 100
 811 ms 13448 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ar = pair<double, int>;

const int mxN = 1e5 + 10;
const double LINF = 1e105;

double ans;
int n, m, h;
bool vis[mxN];
double dis[mxN], dis2[mxN];
vector<pair<int, int>> adj[mxN];
priority_queue<ar, vector<ar>, greater<ar>> pq;

void dijkstra() {
    fill(vis, vis + n + 1, 0);
    for (int i = 0; i < n; i++) if (dis[i] < LINF) pq.push({dis[i], i});
    while (!pq.empty()) {
        auto [D, a] = pq.top();
        pq.pop();
        if (vis[a] or a == h) continue;
        vis[a] = 1;
        for (auto [b, w] : adj[a]) if (dis[b] > dis[a] + w) dis[b] = dis[a] + w, pq.push({dis[b], b});
    }
    ans = min(ans, dis[h]);
}

double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi A) {
    n = N, m = M, h = H, K = min(K, 67);
    fill(dis, dis + n, LINF);
    ans = LINF;
    for (int i = 0; i < n; i++) adj[i].clear();
    for (int i = 0; i < m; i++) adj[x[i]].push_back({y[i], c[i]}), adj[y[i]].push_back({x[i], c[i]});
    dis[0] = 0;
    dijkstra();
    if (dis[h] >= LINF) return -1;
    for (int i = 0; i < n; i++) if (dis[i] != LINF) dis[i] = A[i] && i ? LINF : 0;
    for (int i = 0; i <= K; i++) {
        dijkstra();
        fill(dis2, dis2 + n, LINF);
        for (int j = 0; j < n; j++) if (A[j] > 1) for (auto [u, w] : adj[j]) dis2[u] = min(dis2[u], dis[j] / 2 + w);
        for (int j = 0; j < n; j++) dis[j] = dis2[j];
    }

    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3164 KB Correct.
2 Correct 18 ms 3212 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3676 KB Correct.
2 Correct 25 ms 3956 KB Correct.
3 Correct 24 ms 3792 KB Correct.
4 Correct 25 ms 3932 KB Correct.
5 Correct 25 ms 3932 KB Correct.
6 Correct 23 ms 4444 KB Correct.
7 Correct 31 ms 4688 KB Correct.
8 Correct 13 ms 4956 KB Correct.
9 Correct 22 ms 3676 KB Correct.
10 Correct 22 ms 3672 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3936 KB Correct.
2 Correct 26 ms 3920 KB Correct.
3 Correct 24 ms 3676 KB Correct.
4 Correct 26 ms 3744 KB Correct.
5 Correct 25 ms 3872 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 9444 KB Correct.
2 Correct 147 ms 3924 KB Correct.
3 Correct 124 ms 3668 KB Correct.
4 Correct 127 ms 3920 KB Correct.
5 Correct 73 ms 3668 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3676 KB Correct.
2 Correct 21 ms 3932 KB Correct.
3 Correct 21 ms 3932 KB Correct.
4 Correct 22 ms 4944 KB Correct.
5 Correct 18 ms 3676 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3932 KB Correct.
2 Correct 18 ms 3676 KB Correct.
3 Correct 36 ms 10284 KB Correct.
4 Correct 14 ms 4188 KB Correct.
5 Correct 21 ms 3676 KB Correct.
6 Correct 20 ms 3764 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 3924 KB Correct.
2 Correct 14 ms 3164 KB Correct.
3 Correct 304 ms 13448 KB Correct.
4 Correct 210 ms 6984 KB Correct.
5 Correct 310 ms 10340 KB Correct.
6 Correct 115 ms 8652 KB Correct.
7 Correct 213 ms 7000 KB Correct.
8 Correct 165 ms 5072 KB Correct.
9 Correct 68 ms 3840 KB Correct.
10 Correct 64 ms 3928 KB Correct.
11 Correct 141 ms 4944 KB Correct.
12 Correct 82 ms 3920 KB Correct.
13 Correct 82 ms 4436 KB Correct.
14 Correct 201 ms 8476 KB Correct.
15 Correct 192 ms 5968 KB Correct.
16 Correct 70 ms 3872 KB Correct.
17 Correct 93 ms 3920 KB Correct.
18 Correct 79 ms 3924 KB Correct.
19 Correct 242 ms 4816 KB Correct.
20 Correct 5 ms 2908 KB Correct.
21 Correct 6 ms 2908 KB Correct.
22 Correct 9 ms 3312 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 3924 KB Correct.
2 Correct 26 ms 3160 KB Correct.
3 Correct 166 ms 13232 KB Correct.
4 Correct 231 ms 5620 KB Correct.
5 Correct 630 ms 10196 KB Correct.
6 Correct 223 ms 8792 KB Correct.
7 Correct 372 ms 8472 KB Correct.
8 Correct 186 ms 5108 KB Correct.
9 Correct 116 ms 3864 KB Correct.
10 Correct 105 ms 3816 KB Correct.
11 Correct 116 ms 4548 KB Correct.
12 Correct 142 ms 3920 KB Correct.
13 Correct 129 ms 3872 KB Correct.
14 Correct 811 ms 9240 KB Correct.
15 Correct 629 ms 9180 KB Correct.
16 Correct 341 ms 6484 KB Correct.
17 Correct 214 ms 5016 KB Correct.
18 Correct 117 ms 4012 KB Correct.
19 Correct 162 ms 4068 KB Correct.
20 Correct 134 ms 3924 KB Correct.
21 Correct 467 ms 4808 KB Correct.
22 Correct 7 ms 2908 KB Correct.
23 Correct 9 ms 2908 KB Correct.
24 Correct 17 ms 3456 KB Correct.