oj.uz

Submission #1065327

# Submission time Handle Problem Language Result Execution time Memory
1065327 2024-08-19T06:21:58 Z stdfloat Cyberland (APIO23_cyberland) C++17
97 / 100
 730 ms 63312 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, 62);
 
    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 16 ms 856 KB Correct.
2 Correct 15 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1624 KB Correct.
2 Correct 23 ms 1876 KB Correct.
3 Correct 22 ms 1624 KB Correct.
4 Correct 23 ms 1620 KB Correct.
5 Correct 23 ms 1828 KB Correct.
6 Correct 23 ms 4936 KB Correct.
7 Correct 25 ms 4700 KB Correct.
8 Correct 15 ms 8024 KB Correct.
9 Correct 21 ms 1372 KB Correct.
10 Correct 22 ms 1280 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1616 KB Correct.
2 Correct 24 ms 1840 KB Correct.
3 Correct 21 ms 1628 KB Correct.
4 Correct 37 ms 1420 KB Correct.
5 Correct 24 ms 1372 KB Correct.
6 Correct 7 ms 3672 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 24776 KB Correct.
2 Correct 190 ms 2016 KB Correct.
3 Correct 166 ms 2064 KB Correct.
4 Correct 178 ms 1968 KB Correct.
5 Correct 149 ms 1456 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1632 KB Correct.
2 Correct 19 ms 1844 KB Correct.
3 Correct 26 ms 1760 KB Correct.
4 Correct 20 ms 4444 KB Correct.
5 Correct 19 ms 1356 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1584 KB Correct.
2 Correct 19 ms 1676 KB Correct.
3 Correct 29 ms 9016 KB Correct.
4 Correct 16 ms 3296 KB Correct.
5 Correct 28 ms 1372 KB Correct.
6 Correct 29 ms 1708 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 2028 KB Correct.
2 Correct 25 ms 1860 KB Correct.
3 Correct 612 ms 30392 KB Correct.
4 Correct 493 ms 9756 KB Correct.
5 Correct 730 ms 50328 KB Correct.
6 Correct 375 ms 25380 KB Correct.
7 Correct 493 ms 8572 KB Correct.
8 Correct 457 ms 2960 KB Correct.
9 Correct 165 ms 1444 KB Correct.
10 Correct 143 ms 2156 KB Correct.
11 Correct 435 ms 2096 KB Correct.
12 Correct 183 ms 2148 KB Correct.
13 Correct 191 ms 2056 KB Correct.
14 Correct 437 ms 10524 KB Correct.
15 Correct 482 ms 4516 KB Correct.
16 Correct 149 ms 1944 KB Correct.
17 Correct 193 ms 1964 KB Correct.
18 Correct 199 ms 1828 KB Correct.
19 Correct 406 ms 2496 KB Correct.
20 Correct 15 ms 604 KB Correct.
21 Correct 13 ms 1128 KB Correct.
22 Correct 27 ms 3332 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 3256 KB Correct.
2 Correct 78 ms 4392 KB Correct.
3 Incorrect 561 ms 63312 KB Wrong Answer.
4 Halted 0 ms 0 KB -