oj.uz

Submission #1065323

# Submission time Handle Problem Language Result Execution time Memory
1065323 2024-08-19T06:20:57 Z stdfloat Cyberland (APIO23_cyberland) C++17
97 / 100
 658 ms 62036 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, 60);
 
    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 15 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 18 ms 1628 KB Correct.
2 Correct 24 ms 1840 KB Correct.
3 Correct 21 ms 1712 KB Correct.
4 Correct 22 ms 1728 KB Correct.
5 Correct 22 ms 1824 KB Correct.
6 Correct 25 ms 4932 KB Correct.
7 Correct 28 ms 4700 KB Correct.
8 Correct 16 ms 8024 KB Correct.
9 Correct 21 ms 1372 KB Correct.
10 Correct 19 ms 1292 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1708 KB Correct.
2 Correct 23 ms 1708 KB Correct.
3 Correct 23 ms 1624 KB Correct.
4 Correct 21 ms 1372 KB Correct.
5 Correct 23 ms 1368 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 24888 KB Correct.
2 Correct 207 ms 1816 KB Correct.
3 Correct 169 ms 1928 KB Correct.
4 Correct 166 ms 1976 KB Correct.
5 Correct 147 ms 1360 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 1888 KB Correct.
3 Correct 19 ms 1760 KB Correct.
4 Correct 27 ms 4444 KB Correct.
5 Correct 16 ms 1116 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1688 KB Correct.
2 Correct 21 ms 1616 KB Correct.
3 Correct 28 ms 9184 KB Correct.
4 Correct 16 ms 3268 KB Correct.
5 Correct 18 ms 1368 KB Correct.
6 Correct 19 ms 1712 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 2072 KB Correct.
2 Correct 29 ms 1764 KB Correct.
3 Correct 573 ms 30580 KB Correct.
4 Correct 482 ms 9908 KB Correct.
5 Correct 658 ms 49856 KB Correct.
6 Correct 308 ms 25272 KB Correct.
7 Correct 441 ms 8552 KB Correct.
8 Correct 455 ms 2960 KB Correct.
9 Correct 148 ms 2128 KB Correct.
10 Correct 143 ms 2232 KB Correct.
11 Correct 444 ms 2592 KB Correct.
12 Correct 162 ms 2300 KB Correct.
13 Correct 174 ms 2420 KB Correct.
14 Correct 381 ms 11036 KB Correct.
15 Correct 436 ms 5080 KB Correct.
16 Correct 145 ms 2204 KB Correct.
17 Correct 189 ms 2196 KB Correct.
18 Correct 167 ms 2128 KB Correct.
19 Correct 371 ms 3004 KB Correct.
20 Correct 12 ms 600 KB Correct.
21 Correct 11 ms 1120 KB Correct.
22 Correct 26 ms 3284 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 3516 KB Correct.
2 Correct 68 ms 4272 KB Correct.
3 Incorrect 420 ms 62036 KB Wrong Answer.
4 Halted 0 ms 0 KB -