oj.uz

Submission #1065331

# Submission time Handle Problem Language Result Execution time Memory
1065331 2024-08-19T06:22:50 Z stdfloat Cyberland (APIO23_cyberland) C++17
97 / 100
 636 ms 66344 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, 65);
 
    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 860 KB Correct.
2 Correct 15 ms 820 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1624 KB Correct.
2 Correct 26 ms 1436 KB Correct.
3 Correct 29 ms 1628 KB Correct.
4 Correct 22 ms 1372 KB Correct.
5 Correct 22 ms 1872 KB Correct.
6 Correct 21 ms 4680 KB Correct.
7 Correct 26 ms 4188 KB Correct.
8 Correct 14 ms 8024 KB Correct.
9 Correct 19 ms 1116 KB Correct.
10 Correct 20 ms 1116 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1372 KB Correct.
2 Correct 23 ms 1452 KB Correct.
3 Correct 22 ms 1612 KB Correct.
4 Correct 30 ms 1120 KB Correct.
5 Correct 21 ms 1116 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 24388 KB Correct.
2 Correct 185 ms 1640 KB Correct.
3 Correct 158 ms 1692 KB Correct.
4 Correct 168 ms 1724 KB Correct.
5 Correct 158 ms 1104 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1452 KB Correct.
2 Correct 21 ms 1536 KB Correct.
3 Correct 20 ms 1500 KB Correct.
4 Correct 20 ms 4188 KB Correct.
5 Correct 17 ms 1112 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1372 KB Correct.
2 Correct 17 ms 1496 KB Correct.
3 Correct 30 ms 8572 KB Correct.
4 Correct 13 ms 3268 KB Correct.
5 Correct 18 ms 1224 KB Correct.
6 Correct 19 ms 1524 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 1780 KB Correct.
2 Correct 25 ms 1648 KB Correct.
3 Correct 584 ms 29812 KB Correct.
4 Correct 472 ms 9148 KB Correct.
5 Correct 636 ms 49548 KB Correct.
6 Correct 346 ms 24760 KB Correct.
7 Correct 443 ms 8292 KB Correct.
8 Correct 453 ms 2472 KB Correct.
9 Correct 161 ms 1632 KB Correct.
10 Correct 141 ms 2360 KB Correct.
11 Correct 435 ms 2176 KB Correct.
12 Correct 160 ms 2128 KB Correct.
13 Correct 176 ms 2160 KB Correct.
14 Correct 384 ms 10772 KB Correct.
15 Correct 457 ms 4860 KB Correct.
16 Correct 147 ms 2164 KB Correct.
17 Correct 184 ms 2212 KB Correct.
18 Correct 166 ms 1796 KB Correct.
19 Correct 374 ms 2652 KB Correct.
20 Correct 12 ms 600 KB Correct.
21 Correct 11 ms 1048 KB Correct.
22 Correct 25 ms 3328 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 3628 KB Correct.
2 Correct 74 ms 4708 KB Correct.
3 Incorrect 473 ms 66344 KB Wrong Answer.
4 Halted 0 ms 0 KB -