oj.uz

Submission #836710

# Submission time Handle Problem Language Result Execution time Memory
836710 2023-08-24T14:24:21 Z SoulKnight Cyberland (APIO23_cyberland) C++17
97 / 100
 764 ms 87692 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 * p2[cnt] + e < dist[v][cnt] * p2[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 3028 KB Correct.
2 Correct 26 ms 3028 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4308 KB Correct.
2 Correct 37 ms 4292 KB Correct.
3 Correct 35 ms 4312 KB Correct.
4 Correct 37 ms 4304 KB Correct.
5 Correct 36 ms 4300 KB Correct.
6 Correct 41 ms 12068 KB Correct.
7 Correct 44 ms 11852 KB Correct.
8 Correct 26 ms 20308 KB Correct.
9 Correct 35 ms 3540 KB Correct.
10 Correct 33 ms 3572 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4300 KB Correct.
2 Correct 30 ms 4564 KB Correct.
3 Correct 28 ms 4556 KB Correct.
4 Correct 31 ms 3680 KB Correct.
5 Correct 32 ms 3696 KB Correct.
6 Correct 9 ms 10068 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 53796 KB Correct.
2 Correct 36 ms 4556 KB Correct.
3 Correct 35 ms 4564 KB Correct.
4 Correct 36 ms 4564 KB Correct.
5 Correct 65 ms 3660 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4428 KB Correct.
2 Correct 34 ms 4576 KB Correct.
3 Correct 33 ms 4532 KB Correct.
4 Correct 33 ms 12464 KB Correct.
5 Correct 30 ms 3540 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4428 KB Correct.
2 Correct 27 ms 4564 KB Correct.
3 Correct 72 ms 70316 KB Correct.
4 Correct 24 ms 9712 KB Correct.
5 Correct 31 ms 3660 KB Correct.
6 Correct 29 ms 4692 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 4684 KB Correct.
2 Correct 19 ms 4436 KB Correct.
3 Correct 764 ms 87692 KB Correct.
4 Correct 283 ms 23864 KB Correct.
5 Correct 328 ms 39680 KB Correct.
6 Correct 202 ms 18816 KB Correct.
7 Correct 356 ms 25572 KB Correct.
8 Correct 166 ms 7768 KB Correct.
9 Correct 82 ms 4828 KB Correct.
10 Correct 82 ms 4812 KB Correct.
11 Correct 134 ms 5808 KB Correct.
12 Correct 89 ms 4812 KB Correct.
13 Correct 96 ms 4832 KB Correct.
14 Correct 421 ms 44768 KB Correct.
15 Correct 320 ms 15692 KB Correct.
16 Correct 94 ms 4796 KB Correct.
17 Correct 90 ms 4836 KB Correct.
18 Correct 82 ms 4820 KB Correct.
19 Correct 129 ms 5564 KB Correct.
20 Correct 10 ms 2900 KB Correct.
21 Correct 12 ms 3616 KB Correct.
22 Correct 17 ms 4460 KB Correct.

Subtask #8
0.0 / 3.0

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