oj.uz

Submission #836742

# Submission time Handle Problem Language Result Execution time Memory
836742 2023-08-24T14:47:11 Z SoulKnight Cyberland (APIO23_cyberland) C++17
100 / 100
 1106 ms 66180 KB 
#include "cyberland.h"
// #include "bits/stdc++.h"
#include <vector>
#include <iostream>
#include <array>
#include <queue>
#include <numeric>
#include <cassert>
#include <set>

using namespace std;

#define ll long long
#define ln '\n'

const int N = 1e5 + 5;
const int LG = 71;
const double INF = 1e16;

vector<array<ll, 2>> adj[N];
double dist[N][LG], p2[LG];
priority_queue<array<double, 3>, vector<array<double, 3>>, greater<array<double, 3>>> pq;
set<int> node;
queue<int> q;
bool seen[N];

double solve(int NN, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    for (int i = 0; i < NN; i++) {adj[i].clear(); seen[i] = 0;}
    node.clear();
    K = min(K, 70);
    p2[0] = 1.0;
    for (int i = 1; i < LG; i++) p2[i] = p2[i-1] * 2.0;

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

    q.push(0); seen[0] = 1;
    while (!q.empty()){
        int cur = q.front(); q.pop();
        if (cur == H) continue;
        for (auto& [e, v]: adj[cur]){
            if (seen[v]) continue;
            seen[v] = 1;
            if (arr[v] == 0) node.insert(v);
            q.push(v);
        }
    }

    for (int i = 0; i < NN; i++){
        for (int j = 0; j < LG; j++) dist[i][j] = INF;
    }
    for (int j = 0; j < LG; j++) dist[H][j] = 0.0;
    pq.push({0.0, H, 0}); // (w, node, # of /2)

    double ans = INF;

    while (!pq.empty()){
        double w = pq.top()[0];
        int u = pq.top()[1];
        int cnt = pq.top()[2];
        pq.pop();

        // cout << w << ' ' << u << ' ' << cnt << ln;
        // cout << (w > dist[u][cnt]) << ln;
        if (w > dist[u][cnt]) continue;
        if (arr[u] == 0 && node.count(u)) {ans = min(ans, w); continue;}
        // cout << "what" << ln;
        for (auto& [e, v]: adj[u]){
            // cout << v << ' ' << dist[v][cnt] << ln;
            if (dist[v][cnt] >= INF || w + e / p2[cnt] < dist[v][cnt]){
                dist[v][cnt] = w + e / p2[cnt];
                pq.push({dist[v][cnt], v, min(K, cnt + (arr[v] == 2))});
            }
        }
    }


    for (int j = 0; j <= K; j++){
        ans = min(ans, dist[0][j]);
        // cout << dist[0][j] << " ";
    }
    ans = ((ans >= INF)? -1: ans);
    return ans;

}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:55:19: warning: narrowing conversion of 'H' from 'int' to 'double' [-Wnarrowing]
   55 |     pq.push({0.0, H, 0}); // (w, node, # of /2)
      |                   ^
cyberland.cpp:74:40: warning: narrowing conversion of 'v' from 'std::tuple_element<1, std::array<long long int, 2> >::type' {aka 'long long int'} to 'double' [-Wnarrowing]
   74 |                 pq.push({dist[v][cnt], v, min(K, cnt + (arr[v] == 2))});
      |                                        ^
cyberland.cpp:74:46: warning: narrowing conversion of '(int)std::min<int>(K, (cnt + (arr.std::vector<int>::operator[](((std::vector<int>::size_type)v)) == 2)))' from 'int' to 'double' [-Wnarrowing]
   74 |                 pq.push({dist[v][cnt], v, min(K, cnt + (arr[v] == 2))});
      |                                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3412 KB Correct.
2 Correct 23 ms 3412 KB Correct.
3 Correct 23 ms 3412 KB Correct.
4 Correct 23 ms 3412 KB Correct.
5 Correct 23 ms 3432 KB Correct.
6 Correct 22 ms 9028 KB Correct.
7 Correct 28 ms 8916 KB Correct.
8 Correct 17 ms 15316 KB Correct.
9 Correct 21 ms 2772 KB Correct.
10 Correct 22 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3412 KB Correct.
2 Correct 20 ms 3384 KB Correct.
3 Correct 19 ms 3412 KB Correct.
4 Correct 22 ms 2772 KB Correct.
5 Correct 21 ms 2772 KB Correct.
6 Correct 7 ms 7892 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 39752 KB Correct.
2 Correct 23 ms 3284 KB Correct.
3 Correct 22 ms 3412 KB Correct.
4 Correct 24 ms 3284 KB Correct.
5 Correct 44 ms 2772 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3540 KB Correct.
2 Correct 22 ms 3412 KB Correct.
3 Correct 28 ms 3412 KB Correct.
4 Correct 23 ms 9428 KB Correct.
5 Correct 20 ms 2780 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3472 KB Correct.
2 Correct 19 ms 3512 KB Correct.
3 Correct 51 ms 51192 KB Correct.
4 Correct 16 ms 7508 KB Correct.
5 Correct 20 ms 2772 KB Correct.
6 Correct 20 ms 3412 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 3540 KB Correct.
2 Correct 13 ms 3796 KB Correct.
3 Correct 532 ms 63712 KB Correct.
4 Correct 195 ms 16904 KB Correct.
5 Correct 249 ms 29456 KB Correct.
6 Correct 136 ms 14624 KB Correct.
7 Correct 230 ms 18000 KB Correct.
8 Correct 118 ms 4980 KB Correct.
9 Correct 61 ms 3564 KB Correct.
10 Correct 54 ms 3532 KB Correct.
11 Correct 89 ms 3672 KB Correct.
12 Correct 61 ms 3572 KB Correct.
13 Correct 58 ms 3540 KB Correct.
14 Correct 244 ms 32472 KB Correct.
15 Correct 225 ms 10844 KB Correct.
16 Correct 65 ms 3520 KB Correct.
17 Correct 65 ms 3532 KB Correct.
18 Correct 57 ms 3660 KB Correct.
19 Correct 86 ms 3424 KB Correct.
20 Correct 7 ms 2772 KB Correct.
21 Correct 7 ms 3284 KB Correct.
22 Correct 12 ms 3924 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 3664 KB Correct.
2 Correct 32 ms 3924 KB Correct.
3 Correct 581 ms 66180 KB Correct.
4 Correct 266 ms 8984 KB Correct.
5 Correct 571 ms 37056 KB Correct.
6 Correct 289 ms 18940 KB Correct.
7 Correct 459 ms 28276 KB Correct.
8 Correct 135 ms 5708 KB Correct.
9 Correct 130 ms 4556 KB Correct.
10 Correct 121 ms 4692 KB Correct.
11 Correct 134 ms 4012 KB Correct.
12 Correct 141 ms 4600 KB Correct.
13 Correct 130 ms 4612 KB Correct.
14 Correct 1106 ms 31408 KB Correct.
15 Correct 905 ms 36488 KB Correct.
16 Correct 416 ms 16588 KB Correct.
17 Correct 173 ms 7060 KB Correct.
18 Correct 147 ms 4576 KB Correct.
19 Correct 141 ms 4564 KB Correct.
20 Correct 126 ms 4560 KB Correct.
21 Correct 198 ms 5440 KB Correct.
22 Correct 15 ms 2900 KB Correct.
23 Correct 15 ms 3400 KB Correct.
24 Correct 23 ms 4500 KB Correct.