oj.uz

Submission #1065329

# Submission time Handle Problem Language Result Execution time Memory
1065329 2024-08-19T06:22:19 Z stdfloat Cyberland (APIO23_cyberland) C++17
97 / 100
 669 ms 63100 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, 64);
 
    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 14 ms 604 KB Correct.
2 Correct 15 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 812 KB Correct.
2 Correct 22 ms 860 KB Correct.
3 Correct 21 ms 860 KB Correct.
4 Correct 22 ms 828 KB Correct.
5 Correct 23 ms 856 KB Correct.
6 Correct 21 ms 3916 KB Correct.
7 Correct 45 ms 3852 KB Correct.
8 Correct 16 ms 7700 KB Correct.
9 Correct 19 ms 344 KB Correct.
10 Correct 19 ms 344 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 604 KB Correct.
2 Correct 23 ms 764 KB Correct.
3 Correct 23 ms 872 KB Correct.
4 Correct 24 ms 348 KB Correct.
5 Correct 21 ms 508 KB Correct.
6 Correct 5 ms 3420 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 23428 KB Correct.
2 Correct 189 ms 992 KB Correct.
3 Correct 158 ms 1056 KB Correct.
4 Correct 170 ms 960 KB Correct.
5 Correct 151 ms 344 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 796 KB Correct.
2 Correct 19 ms 604 KB Correct.
3 Correct 21 ms 784 KB Correct.
4 Correct 20 ms 3928 KB Correct.
5 Correct 18 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 860 KB Correct.
2 Correct 17 ms 732 KB Correct.
3 Correct 29 ms 7256 KB Correct.
4 Correct 14 ms 2756 KB Correct.
5 Correct 17 ms 532 KB Correct.
6 Correct 22 ms 792 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 1168 KB Correct.
2 Correct 25 ms 1704 KB Correct.
3 Correct 588 ms 28204 KB Correct.
4 Correct 475 ms 7612 KB Correct.
5 Correct 669 ms 48544 KB Correct.
6 Correct 316 ms 23732 KB Correct.
7 Correct 460 ms 7528 KB Correct.
8 Correct 443 ms 1820 KB Correct.
9 Correct 147 ms 1376 KB Correct.
10 Correct 140 ms 1396 KB Correct.
11 Correct 433 ms 1020 KB Correct.
12 Correct 164 ms 1460 KB Correct.
13 Correct 176 ms 1500 KB Correct.
14 Correct 383 ms 9512 KB Correct.
15 Correct 449 ms 3288 KB Correct.
16 Correct 146 ms 1436 KB Correct.
17 Correct 183 ms 1172 KB Correct.
18 Correct 168 ms 1176 KB Correct.
19 Correct 370 ms 1212 KB Correct.
20 Correct 12 ms 604 KB Correct.
21 Correct 11 ms 1048 KB Correct.
22 Correct 28 ms 3284 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 2688 KB Correct.
2 Correct 74 ms 4424 KB Correct.
3 Incorrect 479 ms 63100 KB Wrong Answer.
4 Halted 0 ms 0 KB -