oj.uz

Submission #776247

# Submission time Handle Problem Language Result Execution time Memory
776247 2023-07-07T13:37:27 Z Alan Cyberland (APIO23_cyberland) C++17
100 / 100
 2286 ms 92632 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, 120);
    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);
            }
        }
    }
    using T = node;
    priority_queue<T, vector<T>, greater<T>> 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 23 ms 472 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 692 KB Correct.
2 Correct 33 ms 808 KB Correct.
3 Correct 24 ms 724 KB Correct.
4 Correct 25 ms 728 KB Correct.
5 Correct 25 ms 704 KB Correct.
6 Correct 22 ms 4068 KB Correct.
7 Correct 29 ms 4052 KB Correct.
8 Correct 14 ms 7832 KB Correct.
9 Correct 24 ms 412 KB Correct.
10 Correct 24 ms 412 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 680 KB Correct.
2 Correct 31 ms 716 KB Correct.
3 Correct 25 ms 760 KB Correct.
4 Correct 26 ms 400 KB Correct.
5 Correct 25 ms 400 KB Correct.
6 Correct 6 ms 3540 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 22656 KB Correct.
2 Correct 128 ms 724 KB Correct.
3 Correct 105 ms 708 KB Correct.
4 Correct 113 ms 716 KB Correct.
5 Correct 79 ms 396 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 640 KB Correct.
2 Correct 25 ms 660 KB Correct.
3 Correct 24 ms 688 KB Correct.
4 Correct 25 ms 3804 KB Correct.
5 Correct 21 ms 388 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 724 KB Correct.
2 Correct 22 ms 696 KB Correct.
3 Correct 44 ms 29260 KB Correct.
4 Correct 16 ms 2804 KB Correct.
5 Correct 29 ms 396 KB Correct.
6 Correct 23 ms 732 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 620 KB Correct.
2 Correct 20 ms 852 KB Correct.
3 Correct 651 ms 27804 KB Correct.
4 Correct 243 ms 9220 KB Correct.
5 Correct 689 ms 20496 KB Correct.
6 Correct 229 ms 11332 KB Correct.
7 Correct 245 ms 9004 KB Correct.
8 Correct 223 ms 2860 KB Correct.
9 Correct 112 ms 1584 KB Correct.
10 Correct 110 ms 1488 KB Correct.
11 Correct 198 ms 2588 KB Correct.
12 Correct 126 ms 1488 KB Correct.
13 Correct 133 ms 1504 KB Correct.
14 Correct 227 ms 11016 KB Correct.
15 Correct 217 ms 4740 KB Correct.
16 Correct 118 ms 1588 KB Correct.
17 Correct 138 ms 1732 KB Correct.
18 Correct 132 ms 1668 KB Correct.
19 Correct 341 ms 2640 KB Correct.
20 Correct 8 ms 460 KB Correct.
21 Correct 9 ms 596 KB Correct.
22 Correct 17 ms 1472 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 1388 KB Correct.
2 Correct 66 ms 2004 KB Correct.
3 Correct 1225 ms 92632 KB Correct.
4 Correct 341 ms 4676 KB Correct.
5 Correct 2286 ms 45812 KB Correct.
6 Correct 887 ms 18172 KB Correct.
7 Correct 745 ms 21628 KB Correct.
8 Correct 371 ms 3136 KB Correct.
9 Correct 378 ms 2320 KB Correct.
10 Correct 363 ms 2240 KB Correct.
11 Correct 195 ms 1528 KB Correct.
12 Correct 407 ms 2352 KB Correct.
13 Correct 410 ms 2344 KB Correct.
14 Correct 1745 ms 41884 KB Correct.
15 Correct 1647 ms 54748 KB Correct.
16 Correct 466 ms 12924 KB Correct.
17 Correct 379 ms 5044 KB Correct.
18 Correct 396 ms 1964 KB Correct.
19 Correct 464 ms 1680 KB Correct.
20 Correct 464 ms 1684 KB Correct.
21 Correct 1254 ms 1448 KB Correct.
22 Correct 21 ms 468 KB Correct.
23 Correct 29 ms 1216 KB Correct.
24 Correct 60 ms 1992 KB Correct.