oj.uz

답안 #1065321

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065321 2024-08-19T06:19:29 Z stdfloat 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 93316 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()) {
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 856 KB Correct.
2 Correct 14 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 1564 KB Correct.
2 Correct 22 ms 1876 KB Correct.
3 Correct 20 ms 1624 KB Correct.
4 Correct 22 ms 1884 KB Correct.
5 Correct 21 ms 1704 KB Correct.
6 Correct 20 ms 4940 KB Correct.
7 Correct 25 ms 4700 KB Correct.
8 Correct 14 ms 8028 KB Correct.
9 Correct 19 ms 1372 KB Correct.
10 Correct 19 ms 1284 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1624 KB Correct.
2 Correct 24 ms 1740 KB Correct.
3 Correct 25 ms 1632 KB Correct.
4 Correct 21 ms 1372 KB Correct.
5 Correct 21 ms 1280 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 24776 KB Correct.
2 Correct 183 ms 1944 KB Correct.
3 Correct 158 ms 1940 KB Correct.
4 Correct 166 ms 1984 KB Correct.
5 Correct 146 ms 1364 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 1628 KB Correct.
2 Correct 19 ms 1812 KB Correct.
3 Correct 19 ms 1760 KB Correct.
4 Correct 20 ms 4444 KB Correct.
5 Correct 15 ms 1116 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 1800 KB Correct.
2 Correct 17 ms 1688 KB Correct.
3 Correct 28 ms 9076 KB Correct.
4 Correct 13 ms 3264 KB Correct.
5 Correct 18 ms 1224 KB Correct.
6 Correct 19 ms 1708 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 2076 KB Correct.
2 Correct 25 ms 1704 KB Correct.
3 Correct 553 ms 30588 KB Correct.
4 Correct 479 ms 9844 KB Correct.
5 Correct 624 ms 50332 KB Correct.
6 Correct 315 ms 25276 KB Correct.
7 Correct 442 ms 8708 KB Correct.
8 Correct 439 ms 3216 KB Correct.
9 Correct 157 ms 2116 KB Correct.
10 Correct 154 ms 2408 KB Correct.
11 Correct 430 ms 2616 KB Correct.
12 Correct 159 ms 2296 KB Correct.
13 Correct 196 ms 2424 KB Correct.
14 Correct 374 ms 11032 KB Correct.
15 Correct 441 ms 5356 KB Correct.
16 Correct 148 ms 2196 KB Correct.
17 Correct 184 ms 2196 KB Correct.
18 Correct 165 ms 2048 KB Correct.
19 Correct 376 ms 3204 KB Correct.
20 Correct 13 ms 600 KB Correct.
21 Correct 11 ms 1112 KB Correct.
22 Correct 25 ms 3284 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 565 ms 3604 KB Correct.
2 Correct 76 ms 4644 KB Correct.
3 Correct 500 ms 67180 KB Correct.
4 Correct 992 ms 6440 KB Correct.
5 Correct 2155 ms 93316 KB Correct.
6 Correct 1114 ms 77432 KB Correct.
7 Correct 1056 ms 25436 KB Correct.
8 Correct 1142 ms 3940 KB Correct.
9 Correct 498 ms 5044 KB Correct.
10 Correct 476 ms 4904 KB Correct.
11 Execution timed out 3071 ms 1528 KB Time limit exceeded
12 Halted 0 ms 0 KB -