oj.uz

Submission #753426

# Submission time Handle Problem Language Result Execution time Memory
753426 2023-06-05T07:59:40 Z Jomnoi Cyberland (APIO23_cyberland) C++17
97 / 100
 1242 ms 64640 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;

const int MAX_N = 1e5 + 5;
const int MAX_K = 71;
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) {
    K = min(K, 65);

    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

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2772 KB Correct.
2 Correct 22 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3340 KB Correct.
2 Correct 28 ms 3328 KB Correct.
3 Correct 26 ms 3316 KB Correct.
4 Correct 27 ms 3348 KB Correct.
5 Correct 28 ms 3436 KB Correct.
6 Correct 25 ms 8812 KB Correct.
7 Correct 31 ms 8672 KB Correct.
8 Correct 18 ms 14932 KB Correct.
9 Correct 24 ms 2772 KB Correct.
10 Correct 23 ms 2784 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3328 KB Correct.
2 Correct 27 ms 3340 KB Correct.
3 Correct 24 ms 3412 KB Correct.
4 Correct 28 ms 2776 KB Correct.
5 Correct 26 ms 2772 KB Correct.
6 Correct 9 ms 7764 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 42972 KB Correct.
2 Correct 293 ms 3716 KB Correct.
3 Correct 249 ms 3752 KB Correct.
4 Correct 261 ms 3824 KB Correct.
5 Correct 217 ms 2948 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3412 KB Correct.
2 Correct 25 ms 3308 KB Correct.
3 Correct 24 ms 3308 KB Correct.
4 Correct 28 ms 8852 KB Correct.
5 Correct 21 ms 2760 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3400 KB Correct.
2 Correct 23 ms 3380 KB Correct.
3 Correct 68 ms 49812 KB Correct.
4 Correct 19 ms 7252 KB Correct.
5 Correct 24 ms 2772 KB Correct.
6 Correct 23 ms 3412 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 4324 KB Correct.
2 Correct 45 ms 5436 KB Correct.
3 Correct 647 ms 64132 KB Correct.
4 Correct 528 ms 16996 KB Correct.
5 Correct 1242 ms 59964 KB Correct.
6 Correct 672 ms 45196 KB Correct.
7 Correct 519 ms 18272 KB Correct.
8 Correct 487 ms 5204 KB Correct.
9 Correct 279 ms 4872 KB Correct.
10 Correct 265 ms 4352 KB Correct.
11 Correct 479 ms 3832 KB Correct.
12 Correct 281 ms 4500 KB Correct.
13 Correct 306 ms 4400 KB Correct.
14 Correct 446 ms 32924 KB Correct.
15 Correct 474 ms 11184 KB Correct.
16 Correct 268 ms 4236 KB Correct.
17 Correct 325 ms 4252 KB Correct.
18 Correct 318 ms 4240 KB Correct.
19 Correct 719 ms 4360 KB Correct.
20 Correct 22 ms 3156 KB Correct.
21 Correct 22 ms 3640 KB Correct.
22 Correct 48 ms 5828 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 965 ms 6860 KB Correct.
2 Correct 135 ms 9888 KB Correct.
3 Incorrect 590 ms 64640 KB Wrong Answer.
4 Halted 0 ms 0 KB -