oj.uz

답안 #1065350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065350 2024-08-19T06:31:46 Z stdfloat 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 94584 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<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<pii>> G(n);
    for (int i = 0; i < n; i++) {
        for (auto j : E[i]) {
            if (a[j.ff]) G[i].push_back(j);
        }
    }
    E = G;
 
    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 (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 16 ms 604 KB Correct.
2 Correct 15 ms 600 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 860 KB Correct.
2 Correct 25 ms 900 KB Correct.
3 Correct 38 ms 872 KB Correct.
4 Correct 30 ms 860 KB Correct.
5 Correct 25 ms 856 KB Correct.
6 Correct 23 ms 4580 KB Correct.
7 Correct 30 ms 4556 KB Correct.
8 Correct 14 ms 8796 KB Correct.
9 Correct 31 ms 348 KB Correct.
10 Correct 24 ms 344 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 856 KB Correct.
2 Correct 24 ms 792 KB Correct.
3 Correct 23 ms 860 KB Correct.
4 Correct 25 ms 344 KB Correct.
5 Correct 25 ms 580 KB Correct.
6 Correct 6 ms 3672 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 26556 KB Correct.
2 Correct 189 ms 1028 KB Correct.
3 Correct 163 ms 1012 KB Correct.
4 Correct 166 ms 1048 KB Correct.
5 Correct 152 ms 604 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 848 KB Correct.
2 Correct 21 ms 856 KB Correct.
3 Correct 20 ms 840 KB Correct.
4 Correct 21 ms 4188 KB Correct.
5 Correct 18 ms 564 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 860 KB Correct.
2 Correct 19 ms 864 KB Correct.
3 Correct 28 ms 7256 KB Correct.
4 Correct 14 ms 2744 KB Correct.
5 Correct 22 ms 576 KB Correct.
6 Correct 20 ms 796 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 1180 KB Correct.
2 Correct 25 ms 1692 KB Correct.
3 Correct 572 ms 33908 KB Correct.
4 Correct 473 ms 8996 KB Correct.
5 Correct 629 ms 50668 KB Correct.
6 Correct 304 ms 24992 KB Correct.
7 Correct 466 ms 8896 KB Correct.
8 Correct 456 ms 3248 KB Correct.
9 Correct 156 ms 1492 KB Correct.
10 Correct 141 ms 2256 KB Correct.
11 Correct 437 ms 2188 KB Correct.
12 Correct 161 ms 2184 KB Correct.
13 Correct 178 ms 2500 KB Correct.
14 Correct 396 ms 13488 KB Correct.
15 Correct 446 ms 4860 KB Correct.
16 Correct 144 ms 2080 KB Correct.
17 Correct 184 ms 1968 KB Correct.
18 Correct 177 ms 1960 KB Correct.
19 Correct 388 ms 2532 KB Correct.
20 Correct 13 ms 600 KB Correct.
21 Correct 11 ms 900 KB Correct.
22 Correct 25 ms 3388 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 552 ms 3500 KB Correct.
2 Correct 78 ms 4668 KB Correct.
3 Correct 494 ms 71508 KB Correct.
4 Correct 963 ms 6148 KB Correct.
5 Correct 2215 ms 94584 KB Correct.
6 Correct 1149 ms 78716 KB Correct.
7 Correct 1077 ms 25336 KB Correct.
8 Correct 1151 ms 3732 KB Correct.
9 Correct 515 ms 4952 KB Correct.
10 Correct 499 ms 4832 KB Correct.
11 Execution timed out 3028 ms 1524 KB Time limit exceeded
12 Halted 0 ms 0 KB -