oj.uz

Submission #836716

# Submission time Handle Problem Language Result Execution time Memory
836716 2023-08-24T14:28:55 Z SoulKnight Cyberland (APIO23_cyberland) C++17
97 / 100
 793 ms 85300 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 = 50;
const long double INF = 1e16;

vector<array<ll, 2>> adj[N];
long double dist[N][LG], p2[LG];
priority_queue<array<long double, 3>, vector<array<long double, 3>>, greater<array<long 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, LG);
    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)

    long double ans = INF;

    while (!pq.empty()){
        long 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 'long 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 'long 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 'long 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 26 ms 2772 KB Correct.
2 Correct 25 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3668 KB Correct.
2 Correct 39 ms 3540 KB Correct.
3 Correct 37 ms 3540 KB Correct.
4 Correct 41 ms 3612 KB Correct.
5 Correct 38 ms 3668 KB Correct.
6 Correct 42 ms 11324 KB Correct.
7 Correct 47 ms 11200 KB Correct.
8 Correct 29 ms 19924 KB Correct.
9 Correct 36 ms 2804 KB Correct.
10 Correct 36 ms 2808 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3588 KB Correct.
2 Correct 29 ms 3540 KB Correct.
3 Correct 31 ms 3600 KB Correct.
4 Correct 35 ms 2824 KB Correct.
5 Correct 37 ms 2772 KB Correct.
6 Correct 11 ms 9740 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 52992 KB Correct.
2 Correct 38 ms 3584 KB Correct.
3 Correct 36 ms 3540 KB Correct.
4 Correct 43 ms 3540 KB Correct.
5 Correct 80 ms 2792 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3668 KB Correct.
2 Correct 34 ms 3668 KB Correct.
3 Correct 33 ms 3668 KB Correct.
4 Correct 34 ms 11608 KB Correct.
5 Correct 32 ms 2812 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3668 KB Correct.
2 Correct 28 ms 3740 KB Correct.
3 Correct 71 ms 68400 KB Correct.
4 Correct 24 ms 9044 KB Correct.
5 Correct 32 ms 2772 KB Correct.
6 Correct 33 ms 3748 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 3916 KB Correct.
2 Correct 22 ms 4180 KB Correct.
3 Correct 793 ms 85300 KB Correct.
4 Correct 354 ms 21700 KB Correct.
5 Correct 385 ms 37884 KB Correct.
6 Correct 215 ms 17376 KB Correct.
7 Correct 421 ms 23372 KB Correct.
8 Correct 209 ms 5832 KB Correct.
9 Correct 95 ms 3916 KB Correct.
10 Correct 93 ms 3956 KB Correct.
11 Correct 165 ms 3936 KB Correct.
12 Correct 104 ms 3788 KB Correct.
13 Correct 98 ms 3788 KB Correct.
14 Correct 424 ms 42948 KB Correct.
15 Correct 388 ms 13780 KB Correct.
16 Correct 108 ms 3788 KB Correct.
17 Correct 108 ms 3892 KB Correct.
18 Correct 94 ms 3780 KB Correct.
19 Correct 148 ms 3648 KB Correct.
20 Correct 11 ms 2772 KB Correct.
21 Correct 12 ms 3540 KB Correct.
22 Correct 17 ms 4308 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 3976 KB Wrong Answer.
2 Halted 0 ms 0 KB -