oj.uz

Submission #1065278

# Submission time Handle Problem Language Result Execution time Memory
1065278 2024-08-19T05:49:25 Z stdfloat Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 168180 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
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, (int)1e2);
 
    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]) 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], {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 16 ms 856 KB Correct.
2 Correct 22 ms 856 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1628 KB Correct.
2 Correct 22 ms 1876 KB Correct.
3 Correct 23 ms 1712 KB Correct.
4 Correct 29 ms 1616 KB Correct.
5 Correct 25 ms 1824 KB Correct.
6 Correct 22 ms 4936 KB Correct.
7 Correct 29 ms 4696 KB Correct.
8 Correct 14 ms 8028 KB Correct.
9 Correct 20 ms 1372 KB Correct.
10 Correct 19 ms 1368 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1628 KB Correct.
2 Correct 23 ms 1704 KB Correct.
3 Correct 22 ms 1676 KB Correct.
4 Correct 21 ms 1372 KB Correct.
5 Correct 21 ms 1368 KB Correct.
6 Correct 6 ms 3672 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 24772 KB Correct.
2 Correct 186 ms 1948 KB Correct.
3 Correct 160 ms 1948 KB Correct.
4 Correct 168 ms 1916 KB Correct.
5 Correct 154 ms 1296 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1628 KB Correct.
2 Correct 20 ms 1880 KB Correct.
3 Correct 19 ms 1764 KB Correct.
4 Correct 20 ms 4480 KB Correct.
5 Correct 16 ms 1116 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1628 KB Correct.
2 Correct 24 ms 1588 KB Correct.
3 Correct 28 ms 9052 KB Correct.
4 Correct 13 ms 3264 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 168 ms 2076 KB Correct.
2 Correct 25 ms 1864 KB Correct.
3 Correct 607 ms 30656 KB Correct.
4 Correct 457 ms 9904 KB Correct.
5 Correct 648 ms 50328 KB Correct.
6 Correct 303 ms 25276 KB Correct.
7 Correct 437 ms 8548 KB Correct.
8 Correct 462 ms 3240 KB Correct.
9 Correct 149 ms 2128 KB Correct.
10 Correct 141 ms 2412 KB Correct.
11 Correct 463 ms 2732 KB Correct.
12 Correct 180 ms 2548 KB Correct.
13 Correct 176 ms 2260 KB Correct.
14 Correct 388 ms 11128 KB Correct.
15 Correct 449 ms 5288 KB Correct.
16 Correct 155 ms 2180 KB Correct.
17 Correct 195 ms 2196 KB Correct.
18 Correct 186 ms 2040 KB Correct.
19 Correct 395 ms 3392 KB Correct.
20 Correct 16 ms 600 KB Correct.
21 Correct 11 ms 1112 KB Correct.
22 Correct 26 ms 3284 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 948 ms 5648 KB Correct.
2 Correct 131 ms 7740 KB Correct.
3 Correct 855 ms 93816 KB Correct.
4 Correct 1393 ms 9172 KB Correct.
5 Execution timed out 3041 ms 168180 KB Time limit exceeded
6 Halted 0 ms 0 KB -