oj.uz

답안 #753418

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753418 2023-06-05T07:44:17 Z Jomnoi 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 49984 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;

const int MAX_N = 1e5 + 5;
const int MAX_K = 35;
const long long INF = 1e18 + 7;

vector <pair <int, int>> graph[MAX_N];
double dist[MAX_N][MAX_K];
bool visited[MAX_N];

double solve(int N, int M, int K, int H, vector <int> x, vector <int> y, vector <int> c, vector <int> arr) {
    for (int i = 0; i < N; i++) {
        graph[i].clear();
        visited[i] = false;
        for (int k = 0; k <= K; k++) {
            dist[i][k] = INF;
        }
    }

    for (int i = 0; i < M; i++) {
        graph[x[i]].emplace_back(y[i], c[i]);
        graph[y[i]].emplace_back(x[i], c[i]);
    }

    queue <int> q;
    q.push(0);
    visited[0] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (auto [v, c] : graph[u]) {
            if (visited[v] == true or v == H) continue;

            visited[v] = true;
            q.push(v);
        }
    }

    priority_queue <tuple <double, int, int>> pq;
    arr[0] = 0;
    for (int i = 0; i < N; i++) {
        if (visited[i] == false or arr[i] != 0) continue;

        pq.emplace(0, 0, i);
        dist[i][0] = 0;
    }

    while (!pq.empty()) {
        auto [d, k, u] = pq.top();
        pq.pop();

        if (dist[u][k] < d or u == H) continue;

        for (auto [v, c] : graph[u]) {
            if (dist[u][k] + c < dist[v][k]) {
                dist[v][k] = dist[u][k] + c;
                pq.emplace(-dist[v][k], k, v);
            }
            if (arr[v] == 2 and k < K and (dist[u][k] + c) / 2.0 < dist[v][k + 1]) {
                dist[v][k + 1] = (dist[u][k] + c) / 2.0;
                pq.emplace(-dist[v][k + 1], k + 1, v);
            }
        }
    }

    double res = INF;
    for (int k = 0; k <= K; k++) res = min(res, dist[H][k]);

    if (res == INF) res = -1;
    return res;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 2772 KB Correct.
2 Correct 22 ms 2760 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 3028 KB Correct.
2 Correct 25 ms 3036 KB Correct.
3 Correct 24 ms 3096 KB Correct.
4 Correct 25 ms 3028 KB Correct.
5 Correct 29 ms 3052 KB Correct.
6 Correct 24 ms 6028 KB Correct.
7 Correct 29 ms 5972 KB Correct.
8 Correct 23 ms 9428 KB Correct.
9 Correct 26 ms 2644 KB Correct.
10 Correct 26 ms 2868 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 3060 KB Correct.
2 Correct 26 ms 3060 KB Correct.
3 Correct 26 ms 3096 KB Correct.
4 Correct 27 ms 2740 KB Correct.
5 Correct 28 ms 2752 KB Correct.
6 Correct 10 ms 5468 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 26452 KB Correct.
2 Correct 279 ms 3428 KB Correct.
3 Correct 245 ms 3456 KB Correct.
4 Correct 267 ms 3476 KB Correct.
5 Correct 216 ms 2796 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 3136 KB Correct.
2 Correct 24 ms 3052 KB Correct.
3 Correct 25 ms 3120 KB Correct.
4 Correct 25 ms 6172 KB Correct.
5 Correct 21 ms 2644 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 3080 KB Correct.
2 Correct 27 ms 3156 KB Correct.
3 Correct 55 ms 28576 KB Correct.
4 Correct 18 ms 5240 KB Correct.
5 Correct 24 ms 2748 KB Correct.
6 Correct 22 ms 3044 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 315 ms 4072 KB Correct.
2 Correct 45 ms 5036 KB Correct.
3 Correct 725 ms 37392 KB Correct.
4 Correct 582 ms 10952 KB Correct.
5 Correct 1231 ms 49984 KB Correct.
6 Correct 685 ms 42324 KB Correct.
7 Correct 517 ms 11504 KB Correct.
8 Correct 522 ms 4128 KB Correct.
9 Correct 294 ms 4556 KB Correct.
10 Correct 273 ms 4092 KB Correct.
11 Correct 519 ms 3448 KB Correct.
12 Correct 301 ms 4092 KB Correct.
13 Correct 329 ms 4044 KB Correct.
14 Correct 467 ms 19860 KB Correct.
15 Correct 503 ms 7680 KB Correct.
16 Correct 295 ms 4048 KB Correct.
17 Correct 357 ms 3924 KB Correct.
18 Correct 344 ms 4024 KB Correct.
19 Correct 748 ms 3904 KB Correct.
20 Correct 22 ms 3028 KB Correct.
21 Correct 23 ms 3468 KB Correct.
22 Correct 48 ms 5448 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3059 ms 21432 KB Time limit exceeded
2 Halted 0 ms 0 KB -