oj.uz

Submission #754134

# Submission time Handle Problem Language Result Execution time Memory
754134 2023-06-06T19:24:12 Z MarwenElarbi Cyberland (APIO23_cyberland) C++17
100 / 100
 164 ms 64608 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 25 ms 2772 KB Correct.
2 Correct 21 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3284 KB Correct.
2 Correct 22 ms 3284 KB Correct.
3 Correct 23 ms 3368 KB Correct.
4 Correct 22 ms 3516 KB Correct.
5 Correct 22 ms 3356 KB Correct.
6 Correct 19 ms 8756 KB Correct.
7 Correct 27 ms 8680 KB Correct.
8 Correct 15 ms 14804 KB Correct.
9 Correct 21 ms 2792 KB Correct.
10 Correct 21 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3324 KB Correct.
2 Correct 20 ms 3364 KB Correct.
3 Correct 18 ms 3372 KB Correct.
4 Correct 21 ms 2772 KB Correct.
5 Correct 21 ms 2772 KB Correct.
6 Correct 7 ms 7636 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 38624 KB Correct.
2 Correct 22 ms 3356 KB Correct.
3 Correct 21 ms 3308 KB Correct.
4 Correct 21 ms 3344 KB Correct.
5 Correct 24 ms 2776 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3412 KB Correct.
2 Correct 26 ms 3412 KB Correct.
3 Correct 24 ms 3388 KB Correct.
4 Correct 27 ms 8884 KB Correct.
5 Correct 20 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3316 KB Correct.
2 Correct 19 ms 3420 KB Correct.
3 Correct 56 ms 49840 KB Correct.
4 Correct 16 ms 7148 KB Correct.
5 Correct 28 ms 2764 KB Correct.
6 Correct 20 ms 3312 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3412 KB Correct.
2 Correct 4 ms 3796 KB Correct.
3 Correct 69 ms 61932 KB Correct.
4 Correct 52 ms 16244 KB Correct.
5 Correct 45 ms 27028 KB Correct.
6 Correct 32 ms 12244 KB Correct.
7 Correct 47 ms 17460 KB Correct.
8 Correct 40 ms 4932 KB Correct.
9 Correct 20 ms 3436 KB Correct.
10 Correct 19 ms 3412 KB Correct.
11 Correct 40 ms 3644 KB Correct.
12 Correct 21 ms 3360 KB Correct.
13 Correct 20 ms 3404 KB Correct.
14 Correct 55 ms 31564 KB Correct.
15 Correct 47 ms 10520 KB Correct.
16 Correct 22 ms 3404 KB Correct.
17 Correct 22 ms 3536 KB Correct.
18 Correct 21 ms 3420 KB Correct.
19 Correct 40 ms 3284 KB Correct.
20 Correct 3 ms 2772 KB Correct.
21 Correct 3 ms 3156 KB Correct.
22 Correct 4 ms 3540 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3420 KB Correct.
2 Correct 5 ms 3796 KB Correct.
3 Correct 94 ms 64608 KB Correct.
4 Correct 41 ms 6732 KB Correct.
5 Correct 49 ms 27084 KB Correct.
6 Correct 31 ms 12296 KB Correct.
7 Correct 52 ms 25064 KB Correct.
8 Correct 42 ms 3736 KB Correct.
9 Correct 24 ms 3476 KB Correct.
10 Correct 22 ms 3416 KB Correct.
11 Correct 164 ms 2836 KB Correct.
12 Correct 22 ms 3412 KB Correct.
13 Correct 21 ms 3380 KB Correct.
14 Correct 58 ms 27612 KB Correct.
15 Correct 60 ms 33524 KB Correct.
16 Correct 60 ms 13756 KB Correct.
17 Correct 41 ms 4984 KB Correct.
18 Correct 21 ms 3440 KB Correct.
19 Correct 23 ms 3440 KB Correct.
20 Correct 23 ms 3452 KB Correct.
21 Correct 41 ms 3284 KB Correct.
22 Correct 6 ms 2772 KB Correct.
23 Correct 4 ms 3156 KB Correct.
24 Correct 4 ms 3540 KB Correct.