oj.uz

답안 #1065281

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065281 2024-08-19T05:50:55 Z stdfloat 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 92796 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, 68);
 
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 860 KB Correct.
2 Correct 15 ms 884 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 1368 KB Correct.
2 Correct 22 ms 1624 KB Correct.
3 Correct 42 ms 1372 KB Correct.
4 Correct 22 ms 1628 KB Correct.
5 Correct 22 ms 1468 KB Correct.
6 Correct 27 ms 4676 KB Correct.
7 Correct 34 ms 4352 KB Correct.
8 Correct 15 ms 8020 KB Correct.
9 Correct 24 ms 1016 KB Correct.
10 Correct 21 ms 968 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 1568 KB Correct.
2 Correct 25 ms 1512 KB Correct.
3 Correct 22 ms 1372 KB Correct.
4 Correct 23 ms 1016 KB Correct.
5 Correct 22 ms 1104 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 24620 KB Correct.
2 Correct 190 ms 1548 KB Correct.
3 Correct 165 ms 1652 KB Correct.
4 Correct 170 ms 1720 KB Correct.
5 Correct 158 ms 1108 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1392 KB Correct.
2 Correct 34 ms 1628 KB Correct.
3 Correct 21 ms 1532 KB Correct.
4 Correct 30 ms 4096 KB Correct.
5 Correct 16 ms 1024 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 1540 KB Correct.
2 Correct 18 ms 1304 KB Correct.
3 Correct 29 ms 8456 KB Correct.
4 Correct 22 ms 3192 KB Correct.
5 Correct 19 ms 960 KB Correct.
6 Correct 21 ms 1488 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 1820 KB Correct.
2 Correct 25 ms 1704 KB Correct.
3 Correct 692 ms 30044 KB Correct.
4 Correct 471 ms 9268 KB Correct.
5 Correct 723 ms 49680 KB Correct.
6 Correct 350 ms 25016 KB Correct.
7 Correct 455 ms 8296 KB Correct.
8 Correct 470 ms 2676 KB Correct.
9 Correct 156 ms 1756 KB Correct.
10 Correct 158 ms 2000 KB Correct.
11 Correct 462 ms 2080 KB Correct.
12 Correct 165 ms 2068 KB Correct.
13 Correct 181 ms 2020 KB Correct.
14 Correct 401 ms 10488 KB Correct.
15 Correct 467 ms 4548 KB Correct.
16 Correct 159 ms 1932 KB Correct.
17 Correct 190 ms 1900 KB Correct.
18 Correct 174 ms 1816 KB Correct.
19 Correct 383 ms 2472 KB Correct.
20 Correct 12 ms 600 KB Correct.
21 Correct 11 ms 892 KB Correct.
22 Correct 27 ms 3284 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 602 ms 3436 KB Correct.
2 Correct 82 ms 4596 KB Correct.
3 Correct 571 ms 67768 KB Correct.
4 Correct 1030 ms 5620 KB Correct.
5 Correct 2473 ms 92796 KB Correct.
6 Correct 1335 ms 77264 KB Correct.
7 Correct 1165 ms 25128 KB Correct.
8 Correct 1198 ms 3224 KB Correct.
9 Correct 535 ms 4568 KB Correct.
10 Correct 560 ms 4628 KB Correct.
11 Execution timed out 3068 ms 1444 KB Time limit exceeded
12 Halted 0 ms 0 KB -