oj.uz

Submission #776265

# Submission time Handle Problem Language Result Execution time Memory
776265 2023-07-07T14:05:51 Z Sharky Cyberland (APIO23_cyberland) C++17
100 / 100
 1479 ms 77288 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const double INF = 1E18;
 
struct node {
    double di;
    int u, k;
    bool operator < (const node& o) const {
        if (k != o.k) return k > o.k;
        return di > o.di;
    }
};
 
double solve(int32_t N, int32_t M, int32_t K, int32_t H, std::vector<int32_t> x, std::vector<int32_t> y, std::vector<int32_t> c, std::vector<int32_t> arr) {
    K = min(K, 80);
    vector<pair<int, int>> adj[N];
    vector<vector<double>> d(N, vector<double> (K + 1, INF));
    for (int i = 0; i < M; i++) {
        if (x[i] != H) adj[x[i]].push_back({y[i], c[i]});
        if (y[i] != H) adj[y[i]].push_back({x[i], c[i]});
    }
    queue<int> q;
    vector<bool> vis(N, 0);
    vis[0] = 1;
    q.push(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto& [v, w] : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
    priority_queue<node> pq;
    pq.push({0.0, 0, 0});
    d[0][0] = 0.0;
    for (int i = 0; i < N; i++) if (arr[i] == 0 && vis[i]) {
        pq.push({0.0, i, 0});
        d[i][0] = 0.0;
    }
    while (!pq.empty()) {
        auto [di, u, k] = pq.top();
        pq.pop();
        if (di != d[u][k]) continue;
        for (auto& [v, w] : adj[u]) {
            double new_weight = d[u][k] + w;
            if (d[v][k] > new_weight) {
                d[v][k] = new_weight;
                pq.push((node) {d[v][k], v, k});
            }
            if (arr[v] == 2 && k != K) {
                double new_weight = d[u][k] + w;
                new_weight /= 2.0;
                if (d[v][k + 1] > new_weight) {
                    d[v][k + 1] = new_weight;
                    pq.push((node) {d[v][k + 1], v, k + 1});
                }
            }
        }
    }
    double res = *min_element(d[H].begin(), d[H].end());
    if (res >= INF) return -1;
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 468 KB Correct.
2 Correct 18 ms 580 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 832 KB Correct.
2 Correct 27 ms 860 KB Correct.
3 Correct 25 ms 812 KB Correct.
4 Correct 32 ms 820 KB Correct.
5 Correct 26 ms 824 KB Correct.
6 Correct 22 ms 4172 KB Correct.
7 Correct 29 ms 4180 KB Correct.
8 Correct 15 ms 7976 KB Correct.
9 Correct 25 ms 468 KB Correct.
10 Correct 25 ms 480 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 824 KB Correct.
2 Correct 26 ms 844 KB Correct.
3 Correct 24 ms 804 KB Correct.
4 Correct 26 ms 476 KB Correct.
5 Correct 26 ms 444 KB Correct.
6 Correct 7 ms 3640 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 22888 KB Correct.
2 Correct 119 ms 844 KB Correct.
3 Correct 106 ms 844 KB Correct.
4 Correct 113 ms 816 KB Correct.
5 Correct 76 ms 452 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 776 KB Correct.
2 Correct 25 ms 752 KB Correct.
3 Correct 24 ms 844 KB Correct.
4 Correct 24 ms 3972 KB Correct.
5 Correct 25 ms 400 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 768 KB Correct.
2 Correct 21 ms 812 KB Correct.
3 Correct 56 ms 29500 KB Correct.
4 Correct 16 ms 2900 KB Correct.
5 Correct 24 ms 468 KB Correct.
6 Correct 30 ms 800 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 840 KB Correct.
2 Correct 21 ms 980 KB Correct.
3 Correct 611 ms 28028 KB Correct.
4 Correct 259 ms 8560 KB Correct.
5 Correct 672 ms 19956 KB Correct.
6 Correct 223 ms 10656 KB Correct.
7 Correct 242 ms 8312 KB Correct.
8 Correct 215 ms 2264 KB Correct.
9 Correct 111 ms 976 KB Correct.
10 Correct 110 ms 824 KB Correct.
11 Correct 198 ms 1824 KB Correct.
12 Correct 121 ms 920 KB Correct.
13 Correct 121 ms 984 KB Correct.
14 Correct 241 ms 10312 KB Correct.
15 Correct 223 ms 3936 KB Correct.
16 Correct 119 ms 940 KB Correct.
17 Correct 139 ms 972 KB Correct.
18 Correct 131 ms 900 KB Correct.
19 Correct 337 ms 1820 KB Correct.
20 Correct 8 ms 444 KB Correct.
21 Correct 9 ms 596 KB Correct.
22 Correct 16 ms 1464 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 1216 KB Correct.
2 Correct 45 ms 1620 KB Correct.
3 Correct 900 ms 77288 KB Correct.
4 Correct 291 ms 3500 KB Correct.
5 Correct 1479 ms 33956 KB Correct.
6 Correct 610 ms 14180 KB Correct.
7 Correct 518 ms 15212 KB Correct.
8 Correct 322 ms 2080 KB Correct.
9 Correct 258 ms 1264 KB Correct.
10 Correct 253 ms 1328 KB Correct.
11 Correct 164 ms 724 KB Correct.
12 Correct 296 ms 1208 KB Correct.
13 Correct 281 ms 1288 KB Correct.
14 Correct 1367 ms 32108 KB Correct.
15 Correct 1052 ms 38672 KB Correct.
16 Correct 419 ms 12184 KB Correct.
17 Correct 353 ms 3268 KB Correct.
18 Correct 273 ms 1264 KB Correct.
19 Correct 320 ms 1272 KB Correct.
20 Correct 312 ms 1328 KB Correct.
21 Correct 817 ms 1108 KB Correct.
22 Correct 16 ms 440 KB Correct.
23 Correct 21 ms 940 KB Correct.
24 Correct 37 ms 1620 KB Correct.