oj.uz

Submission #1065328

# Submission time Handle Problem Language Result Execution time Memory
1065328 2024-08-19T06:22:09 Z stdfloat Cyberland (APIO23_cyberland) C++17
97 / 100
 678 ms 63060 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
// #include "stub.cpp"
using namespace std;
 
#define ff  first
#define ss  second
#define pii pair<int, int>
 
double solve(int n, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> a) {
    vector<pii> E[n];
    for (int i = 0; i < M; i++) {
        E[X[i]].push_back({Y[i], C[i]});
        E[Y[i]].push_back({X[i], C[i]});
    }
 
    queue<int> q;
    vector<bool> vis0(n);
    q.push(0); vis0[0] = true;
    while (!q.empty()) {
        int x = q.front(); q.pop();
 
        if (x == H) continue;
 
        for (auto [i, w] : E[x]) {
            if (!vis0[i]) {
                q.push(i);
                vis0[i] = true;
            }
        }
    }
 
    if (!vis0[H]) return -1;
 
    K = min(K, 63);
 
    vector<vector<double>> dis(n, vector<double>(K + 1, 1e18));
    priority_queue<pair<double, int>> pq;
    for (int i = 0; i < n; i++) {
        if (!i || (!a[i] && vis0[i])) {
            dis[i][0] = 0;
            pq.push({0, 70 * i});
        }
    }
    while (!pq.empty()) {
        double d = pq.top().ff; d = -d;
        int x = pq.top().ss; pq.pop();
        int y = x % 70; x /= 70;
    
        if (d != dis[x][y]) continue;
 
        if (x == H) continue;
    
        for (auto [i, w] : E[x]) {
            if (!a[i]) continue;
 
            if (d + w < dis[i][y]) {
                dis[i][y] = d + w;
                pq.push({-dis[i][y], y + 70 * i});
            }
            if (a[i] == 2 && y < K && (d + w) / 2 < dis[i][y + 1]) {
                dis[i][y + 1] = (d + w) / 2;
                pq.push({-dis[i][y + 1], y + 1 + 70 * i});
            }
        }
    }
 
    return *min_element(dis[H].begin(), dis[H].end());
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 604 KB Correct.
2 Correct 17 ms 608 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 860 KB Correct.
2 Correct 22 ms 844 KB Correct.
3 Correct 26 ms 816 KB Correct.
4 Correct 26 ms 604 KB Correct.
5 Correct 22 ms 860 KB Correct.
6 Correct 24 ms 4040 KB Correct.
7 Correct 32 ms 3796 KB Correct.
8 Correct 15 ms 7516 KB Correct.
9 Correct 20 ms 348 KB Correct.
10 Correct 26 ms 344 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 600 KB Correct.
2 Correct 28 ms 764 KB Correct.
3 Correct 20 ms 860 KB Correct.
4 Correct 24 ms 512 KB Correct.
5 Correct 22 ms 548 KB Correct.
6 Correct 9 ms 3416 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 23492 KB Correct.
2 Correct 213 ms 964 KB Correct.
3 Correct 158 ms 1032 KB Correct.
4 Correct 178 ms 972 KB Correct.
5 Correct 153 ms 344 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 796 KB Correct.
2 Correct 19 ms 600 KB Correct.
3 Correct 19 ms 784 KB Correct.
4 Correct 20 ms 3672 KB Correct.
5 Correct 17 ms 532 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 852 KB Correct.
2 Correct 18 ms 732 KB Correct.
3 Correct 27 ms 7248 KB Correct.
4 Correct 14 ms 2752 KB Correct.
5 Correct 25 ms 348 KB Correct.
6 Correct 21 ms 800 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 1144 KB Correct.
2 Correct 26 ms 1692 KB Correct.
3 Correct 590 ms 28248 KB Correct.
4 Correct 452 ms 7608 KB Correct.
5 Correct 678 ms 48540 KB Correct.
6 Correct 339 ms 23744 KB Correct.
7 Correct 481 ms 7520 KB Correct.
8 Correct 454 ms 1780 KB Correct.
9 Correct 150 ms 1372 KB Correct.
10 Correct 144 ms 1488 KB Correct.
11 Correct 450 ms 1020 KB Correct.
12 Correct 170 ms 1440 KB Correct.
13 Correct 194 ms 1500 KB Correct.
14 Correct 399 ms 9496 KB Correct.
15 Correct 448 ms 3312 KB Correct.
16 Correct 147 ms 1432 KB Correct.
17 Correct 186 ms 1172 KB Correct.
18 Correct 186 ms 1132 KB Correct.
19 Correct 377 ms 1348 KB Correct.
20 Correct 12 ms 600 KB Correct.
21 Correct 11 ms 1040 KB Correct.
22 Correct 26 ms 3280 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 2816 KB Correct.
2 Correct 72 ms 4464 KB Correct.
3 Incorrect 492 ms 63060 KB Wrong Answer.
4 Halted 0 ms 0 KB -