oj.uz

답안 #1065349

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065349 2024-08-19T06:31:18 Z stdfloat 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 95320 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]) {
            assert(a[i]);
 
            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 860 KB Correct.
2 Correct 15 ms 856 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 1628 KB Correct.
2 Correct 26 ms 1872 KB Correct.
3 Correct 24 ms 1884 KB Correct.
4 Correct 26 ms 1872 KB Correct.
5 Correct 32 ms 1752 KB Correct.
6 Correct 23 ms 5560 KB Correct.
7 Correct 32 ms 5320 KB Correct.
8 Correct 17 ms 9304 KB Correct.
9 Correct 25 ms 1328 KB Correct.
10 Correct 24 ms 1372 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 1692 KB Correct.
2 Correct 26 ms 1816 KB Correct.
3 Correct 23 ms 1820 KB Correct.
4 Correct 35 ms 1404 KB Correct.
5 Correct 25 ms 1372 KB Correct.
6 Correct 7 ms 4004 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 27828 KB Correct.
2 Correct 199 ms 1920 KB Correct.
3 Correct 163 ms 2040 KB Correct.
4 Correct 169 ms 1884 KB Correct.
5 Correct 160 ms 1500 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 1688 KB Correct.
2 Correct 28 ms 1756 KB Correct.
3 Correct 23 ms 1724 KB Correct.
4 Correct 22 ms 4956 KB Correct.
5 Correct 19 ms 1372 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1880 KB Correct.
2 Correct 21 ms 1740 KB Correct.
3 Correct 27 ms 9040 KB Correct.
4 Correct 17 ms 3452 KB Correct.
5 Correct 20 ms 1372 KB Correct.
6 Correct 20 ms 1740 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 168 ms 2032 KB Correct.
2 Correct 25 ms 1792 KB Correct.
3 Correct 573 ms 36324 KB Correct.
4 Correct 465 ms 11104 KB Correct.
5 Correct 643 ms 52376 KB Correct.
6 Correct 324 ms 26556 KB Correct.
7 Correct 458 ms 10076 KB Correct.
8 Correct 448 ms 3268 KB Correct.
9 Correct 157 ms 1344 KB Correct.
10 Correct 142 ms 2268 KB Correct.
11 Correct 440 ms 2740 KB Correct.
12 Correct 167 ms 2356 KB Correct.
13 Correct 176 ms 2460 KB Correct.
14 Correct 388 ms 13792 KB Correct.
15 Correct 446 ms 5612 KB Correct.
16 Correct 154 ms 2264 KB Correct.
17 Correct 191 ms 2156 KB Correct.
18 Correct 170 ms 2120 KB Correct.
19 Correct 379 ms 3256 KB Correct.
20 Correct 12 ms 600 KB Correct.
21 Correct 11 ms 980 KB Correct.
22 Correct 26 ms 3536 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 546 ms 3704 KB Correct.
2 Correct 77 ms 4668 KB Correct.
3 Correct 470 ms 72664 KB Correct.
4 Correct 973 ms 6648 KB Correct.
5 Correct 2199 ms 95320 KB Correct.
6 Correct 1146 ms 78832 KB Correct.
7 Correct 1080 ms 25344 KB Correct.
8 Correct 1137 ms 3880 KB Correct.
9 Correct 509 ms 4912 KB Correct.
10 Correct 486 ms 4888 KB Correct.
11 Execution timed out 3036 ms 1532 KB Time limit exceeded
12 Halted 0 ms 0 KB -