oj.uz

Submission #753464

# Submission time Handle Problem Language Result Execution time Memory
753464 2023-06-05T09:18:11 Z Jomnoi Cyberland (APIO23_cyberland) C++17
100 / 100
 175 ms 64596 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 power[MAX_K], 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, 66);

    power[0] = 1.0;
    for (int i = 1; i <= K; i++) power[i] = power[i - 1] / 2.0;
 
    arr[0] = 0;
    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;
    pq.emplace(0, 0, H);
    dist[H][0] = 0;

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

        if (dist[u][k] < -d) continue;
        if (arr[u] == 0) return -d;
 
        for (auto [v, c] : graph[u]) {
            if (visited[v] == false) continue;

            if (dist[u][k] + power[k] * c < dist[v][k]) {
                dist[v][k] = dist[u][k] + power[k] * c;
                pq.emplace(-dist[v][k], k, v);
            }
            if (arr[v] == 2 and k < K and dist[u][k] + power[k] * c < dist[v][k + 1]) {
                dist[v][k + 1] = dist[u][k] + power[k] * c;
                pq.emplace(-dist[v][k + 1], k + 1, v);
            }
        }
    }
    return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2772 KB Correct.
2 Correct 26 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3344 KB Correct.
2 Correct 23 ms 3348 KB Correct.
3 Correct 24 ms 3284 KB Correct.
4 Correct 23 ms 3412 KB Correct.
5 Correct 22 ms 3284 KB Correct.
6 Correct 28 ms 8788 KB Correct.
7 Correct 30 ms 8660 KB Correct.
8 Correct 15 ms 14804 KB Correct.
9 Correct 23 ms 2784 KB Correct.
10 Correct 22 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3252 KB Correct.
2 Correct 20 ms 3352 KB Correct.
3 Correct 20 ms 3368 KB Correct.
4 Correct 27 ms 2776 KB Correct.
5 Correct 23 ms 2772 KB Correct.
6 Correct 7 ms 7620 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 38740 KB Correct.
2 Correct 21 ms 3284 KB Correct.
3 Correct 20 ms 3284 KB Correct.
4 Correct 29 ms 3336 KB Correct.
5 Correct 27 ms 2900 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3412 KB Correct.
2 Correct 24 ms 3412 KB Correct.
3 Correct 21 ms 3380 KB Correct.
4 Correct 26 ms 8852 KB Correct.
5 Correct 21 ms 2792 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3380 KB Correct.
2 Correct 20 ms 3316 KB Correct.
3 Correct 59 ms 49844 KB Correct.
4 Correct 17 ms 7124 KB Correct.
5 Correct 21 ms 2792 KB Correct.
6 Correct 20 ms 3352 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3412 KB Correct.
2 Correct 5 ms 3708 KB Correct.
3 Correct 99 ms 61996 KB Correct.
4 Correct 52 ms 16252 KB Correct.
5 Correct 49 ms 27028 KB Correct.
6 Correct 33 ms 12288 KB Correct.
7 Correct 54 ms 17492 KB Correct.
8 Correct 42 ms 4948 KB Correct.
9 Correct 20 ms 3412 KB Correct.
10 Correct 19 ms 3388 KB Correct.
11 Correct 41 ms 3644 KB Correct.
12 Correct 21 ms 3412 KB Correct.
13 Correct 20 ms 3412 KB Correct.
14 Correct 56 ms 31608 KB Correct.
15 Correct 46 ms 10444 KB Correct.
16 Correct 26 ms 3436 KB Correct.
17 Correct 23 ms 3428 KB Correct.
18 Correct 21 ms 3396 KB Correct.
19 Correct 40 ms 3284 KB Correct.
20 Correct 4 ms 2772 KB Correct.
21 Correct 4 ms 3200 KB Correct.
22 Correct 5 ms 3540 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3436 KB Correct.
2 Correct 5 ms 3752 KB Correct.
3 Correct 99 ms 64596 KB Correct.
4 Correct 41 ms 6732 KB Correct.
5 Correct 48 ms 27052 KB Correct.
6 Correct 35 ms 12284 KB Correct.
7 Correct 55 ms 25076 KB Correct.
8 Correct 53 ms 3684 KB Correct.
9 Correct 23 ms 3540 KB Correct.
10 Correct 22 ms 3440 KB Correct.
11 Correct 175 ms 2920 KB Correct.
12 Correct 24 ms 3440 KB Correct.
13 Correct 23 ms 3356 KB Correct.
14 Correct 59 ms 27592 KB Correct.
15 Correct 60 ms 33444 KB Correct.
16 Correct 49 ms 13772 KB Correct.
17 Correct 44 ms 4924 KB Correct.
18 Correct 25 ms 3452 KB Correct.
19 Correct 25 ms 3412 KB Correct.
20 Correct 25 ms 3412 KB Correct.
21 Correct 44 ms 3284 KB Correct.
22 Correct 4 ms 2772 KB Correct.
23 Correct 4 ms 3400 KB Correct.
24 Correct 6 ms 3540 KB Correct.