oj.uz

답안 #1065336

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065336 2024-08-19T06:25:05 Z stdfloat 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 91248 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, 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()) {
        auto [d, x] = pq.top(); d = -d; 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

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

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 832 KB Correct.
2 Correct 21 ms 860 KB Correct.
3 Correct 20 ms 860 KB Correct.
4 Correct 21 ms 840 KB Correct.
5 Correct 21 ms 828 KB Correct.
6 Correct 31 ms 3916 KB Correct.
7 Correct 32 ms 3932 KB Correct.
8 Correct 12 ms 7516 KB Correct.
9 Correct 21 ms 532 KB Correct.
10 Correct 19 ms 528 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 604 KB Correct.
2 Correct 22 ms 764 KB Correct.
3 Correct 20 ms 884 KB Correct.
4 Correct 25 ms 516 KB Correct.
5 Correct 21 ms 532 KB Correct.
6 Correct 5 ms 3476 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 23596 KB Correct.
2 Correct 190 ms 988 KB Correct.
3 Correct 160 ms 1056 KB Correct.
4 Correct 179 ms 1008 KB Correct.
5 Correct 153 ms 552 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 796 KB Correct.
2 Correct 19 ms 760 KB Correct.
3 Correct 21 ms 808 KB Correct.
4 Correct 20 ms 3744 KB Correct.
5 Correct 17 ms 536 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 860 KB Correct.
2 Correct 18 ms 732 KB Correct.
3 Correct 33 ms 7300 KB Correct.
4 Correct 15 ms 2656 KB Correct.
5 Correct 19 ms 532 KB Correct.
6 Correct 25 ms 808 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 1156 KB Correct.
2 Correct 27 ms 1692 KB Correct.
3 Correct 627 ms 28376 KB Correct.
4 Correct 458 ms 7644 KB Correct.
5 Correct 637 ms 48448 KB Correct.
6 Correct 324 ms 23812 KB Correct.
7 Correct 438 ms 7460 KB Correct.
8 Correct 447 ms 1668 KB Correct.
9 Correct 147 ms 1380 KB Correct.
10 Correct 140 ms 1348 KB Correct.
11 Correct 440 ms 960 KB Correct.
12 Correct 158 ms 1568 KB Correct.
13 Correct 177 ms 1688 KB Correct.
14 Correct 371 ms 9496 KB Correct.
15 Correct 440 ms 3312 KB Correct.
16 Correct 145 ms 1432 KB Correct.
17 Correct 183 ms 1172 KB Correct.
18 Correct 167 ms 1088 KB Correct.
19 Correct 371 ms 1212 KB Correct.
20 Correct 12 ms 600 KB Correct.
21 Correct 11 ms 1056 KB Correct.
22 Correct 28 ms 3284 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 575 ms 2648 KB Correct.
2 Correct 77 ms 4468 KB Correct.
3 Correct 490 ms 64596 KB Correct.
4 Correct 971 ms 4692 KB Correct.
5 Correct 2188 ms 91248 KB Correct.
6 Correct 1131 ms 75968 KB Correct.
7 Correct 1098 ms 23372 KB Correct.
8 Correct 1110 ms 2084 KB Correct.
9 Correct 509 ms 4692 KB Correct.
10 Correct 482 ms 3968 KB Correct.
11 Execution timed out 3025 ms 468 KB Time limit exceeded
12 Halted 0 ms 0 KB -