oj.uz

Submission #1065325

# Submission time Handle Problem Language Result Execution time Memory
1065325 2024-08-19T06:21:27 Z stdfloat Cyberland (APIO23_cyberland) C++17
97 / 100
 729 ms 62808 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, 61);
 
    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 600 KB Correct.
2 Correct 15 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 808 KB Correct.
2 Correct 22 ms 840 KB Correct.
3 Correct 20 ms 836 KB Correct.
4 Correct 29 ms 604 KB Correct.
5 Correct 22 ms 824 KB Correct.
6 Correct 25 ms 4104 KB Correct.
7 Correct 31 ms 3932 KB Correct.
8 Correct 12 ms 7584 KB Correct.
9 Correct 33 ms 532 KB Correct.
10 Correct 26 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 604 KB Correct.
2 Correct 23 ms 764 KB Correct.
3 Correct 34 ms 844 KB Correct.
4 Correct 21 ms 524 KB Correct.
5 Correct 20 ms 348 KB Correct.
6 Correct 5 ms 3424 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 23488 KB Correct.
2 Correct 203 ms 960 KB Correct.
3 Correct 168 ms 1060 KB Correct.
4 Correct 191 ms 980 KB Correct.
5 Correct 152 ms 344 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 856 KB Correct.
2 Correct 19 ms 600 KB Correct.
3 Correct 24 ms 776 KB Correct.
4 Correct 19 ms 3676 KB Correct.
5 Correct 15 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 816 KB Correct.
2 Correct 20 ms 772 KB Correct.
3 Correct 48 ms 7296 KB Correct.
4 Correct 13 ms 2752 KB Correct.
5 Correct 20 ms 344 KB Correct.
6 Correct 31 ms 832 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 1288 KB Correct.
2 Correct 25 ms 1632 KB Correct.
3 Correct 610 ms 28248 KB Correct.
4 Correct 505 ms 7740 KB Correct.
5 Correct 729 ms 48436 KB Correct.
6 Correct 366 ms 23808 KB Correct.
7 Correct 493 ms 7436 KB Correct.
8 Correct 476 ms 1848 KB Correct.
9 Correct 159 ms 1420 KB Correct.
10 Correct 150 ms 2060 KB Correct.
11 Correct 450 ms 2176 KB Correct.
12 Correct 173 ms 2204 KB Correct.
13 Correct 189 ms 2276 KB Correct.
14 Correct 406 ms 10896 KB Correct.
15 Correct 474 ms 4528 KB Correct.
16 Correct 160 ms 2192 KB Correct.
17 Correct 206 ms 1940 KB Correct.
18 Correct 181 ms 1856 KB Correct.
19 Correct 381 ms 2452 KB Correct.
20 Correct 12 ms 600 KB Correct.
21 Correct 11 ms 1048 KB Correct.
22 Correct 26 ms 3536 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 3452 KB Correct.
2 Correct 76 ms 4504 KB Correct.
3 Incorrect 514 ms 62808 KB Wrong Answer.
4 Halted 0 ms 0 KB -