oj.uz

Submission #1065409

# Submission time Handle Problem Language Result Execution time Memory
1065409 2024-08-19T07:12:10 Z stdfloat Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 91304 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, 66);
 
    vector<vector<double>> dis(n, vector<double>(K + 1, 1e18));
    priority_queue<pair<double, pii>> pq;
    for (int i = 0; i < n; i++) {
        if (!i || (!a[i] && vis0[i])) {
            dis[i][0] = 0;
            pq.push({0, {i, 0}});
        }
    }
    while (!pq.empty()) {
        double d = pq.top().ff; d = -d;
        auto [x, y] = pq.top().ss; pq.pop();
    
        if (d != dis[x][y] || 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], {i, y}});
            }
            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], {i, y + 1}});
            }
        }
    }
 
    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 16 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 856 KB Correct.
2 Correct 22 ms 848 KB Correct.
3 Correct 23 ms 860 KB Correct.
4 Correct 23 ms 604 KB Correct.
5 Correct 24 ms 820 KB Correct.
6 Correct 30 ms 3988 KB Correct.
7 Correct 38 ms 3892 KB Correct.
8 Correct 18 ms 7656 KB Correct.
9 Correct 21 ms 348 KB Correct.
10 Correct 23 ms 536 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 604 KB Correct.
2 Correct 25 ms 760 KB Correct.
3 Correct 24 ms 860 KB Correct.
4 Correct 30 ms 348 KB Correct.
5 Correct 21 ms 348 KB Correct.
6 Correct 6 ms 3420 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 23580 KB Correct.
2 Correct 204 ms 964 KB Correct.
3 Correct 170 ms 1032 KB Correct.
4 Correct 171 ms 1164 KB Correct.
5 Correct 155 ms 576 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 796 KB Correct.
2 Correct 19 ms 600 KB Correct.
3 Correct 19 ms 808 KB Correct.
4 Correct 20 ms 3852 KB Correct.
5 Correct 16 ms 528 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1108 KB Correct.
2 Correct 17 ms 968 KB Correct.
3 Correct 28 ms 7248 KB Correct.
4 Correct 13 ms 2756 KB Correct.
5 Correct 18 ms 524 KB Correct.
6 Correct 19 ms 792 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 1168 KB Correct.
2 Correct 28 ms 1676 KB Correct.
3 Correct 572 ms 28268 KB Correct.
4 Correct 488 ms 7648 KB Correct.
5 Correct 623 ms 48692 KB Correct.
6 Correct 308 ms 24256 KB Correct.
7 Correct 477 ms 7528 KB Correct.
8 Correct 444 ms 1680 KB Correct.
9 Correct 152 ms 1268 KB Correct.
10 Correct 143 ms 1388 KB Correct.
11 Correct 435 ms 972 KB Correct.
12 Correct 166 ms 1496 KB Correct.
13 Correct 176 ms 1512 KB Correct.
14 Correct 376 ms 9412 KB Correct.
15 Correct 470 ms 3412 KB Correct.
16 Correct 146 ms 1416 KB Correct.
17 Correct 187 ms 1176 KB Correct.
18 Correct 168 ms 1080 KB Correct.
19 Correct 374 ms 1212 KB Correct.
20 Correct 12 ms 604 KB Correct.
21 Correct 14 ms 1048 KB Correct.
22 Correct 25 ms 3284 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 2808 KB Correct.
2 Correct 78 ms 4420 KB Correct.
3 Correct 476 ms 64592 KB Correct.
4 Correct 972 ms 4652 KB Correct.
5 Correct 2191 ms 91304 KB Correct.
6 Correct 1169 ms 77640 KB Correct.
7 Correct 1056 ms 24752 KB Correct.
8 Correct 1126 ms 2080 KB Correct.
9 Correct 501 ms 4820 KB Correct.
10 Correct 488 ms 4056 KB Correct.
11 Execution timed out 3064 ms 596 KB Time limit exceeded
12 Halted 0 ms 0 KB -