oj.uz

Submission #978916

# Submission time Handle Problem Language Result Execution time Memory
978916 2024-05-10T02:43:12 Z math_rabbit_1028 Cyberland (APIO23_cyberland) C++17
97 / 100
 1148 ms 71080 KB 
#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

int n, m, k, h;
vector<pll> adj[101010];


int ch[101010];
void DFS(int v) {
    if (v == h) return;
    if (ch[v]) return;
    ch[v] = 1;
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i].first;
        DFS(u);
    }
}

double dis[31][101010];
priority_queue< pair<double, ll> > pq;

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {

    n = N; m = M; k = K; h = H;
    for (int i = 0; i < n; i++) adj[i].clear();

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

    dis[k][0] = 0;
    pq.push({-dis[k][0], k*n+0});
    for (int i = 1; i < n; i++) {
        if (arr[i] == 0 && ch[i] == 1) {
            dis[k][i] = 0;
            pq.push({-dis[k][i], k*n+i});
        }
        else {
            dis[k][i] = 1e18;
        }
    }
    for (int t = 0; t < k; t++) {
        for (int i = 0; i < n; i++) dis[t][i] = 1e18;
    }

    while (!pq.empty()) {
        int v = pq.top().second % n, t = pq.top().second / n; double w = -pq.top().first;
        pq.pop();

        if (dis[t][v] < w) continue;
        if (v == h) continue;

        for (int i = 0; i < adj[v].size(); i++) {
            int u = adj[v][i].first; ll ww = adj[v][i].second;
            if (dis[t][u] > w + ww) {
                dis[t][u] = w + ww;
                pq.push({-dis[t][u], t*n+u});
            }

            if (arr[u] != 2) continue;
            if (t == 0) continue;
            if (dis[t-1][u] > (w + ww) / 2.0) {
                dis[t-1][u] = (w + ww) / 2.0;
                pq.push({-dis[t-1][u], (t-1)*n+u});
            }
        }
    }

    double ans = 1e18;
    for (int t = 0; t <= k; t++) {
        ans = min(ans, dis[t][h]);
    }

    if (ans >= 1e17) return -1;
    else return ans;
}

Compilation message

cyberland.cpp: In function 'void DFS(int)':
cyberland.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int i = 0; i < adj[v].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 27980 KB Correct.
2 Correct 19 ms 27992 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28508 KB Correct.
2 Correct 32 ms 28764 KB Correct.
3 Correct 25 ms 28736 KB Correct.
4 Correct 26 ms 28756 KB Correct.
5 Correct 26 ms 28752 KB Correct.
6 Correct 23 ms 29276 KB Correct.
7 Correct 28 ms 29524 KB Correct.
8 Correct 16 ms 29784 KB Correct.
9 Correct 24 ms 28508 KB Correct.
10 Correct 23 ms 28252 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28508 KB Correct.
2 Correct 25 ms 28504 KB Correct.
3 Correct 27 ms 28756 KB Correct.
4 Correct 26 ms 28368 KB Correct.
5 Correct 25 ms 28696 KB Correct.
6 Correct 9 ms 28504 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 39108 KB Correct.
2 Correct 271 ms 28844 KB Correct.
3 Correct 234 ms 28800 KB Correct.
4 Correct 253 ms 28920 KB Correct.
5 Correct 213 ms 28516 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28508 KB Correct.
2 Correct 24 ms 28764 KB Correct.
3 Correct 24 ms 28764 KB Correct.
4 Correct 25 ms 30044 KB Correct.
5 Correct 22 ms 28252 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28756 KB Correct.
2 Correct 22 ms 28536 KB Correct.
3 Correct 39 ms 35924 KB Correct.
4 Correct 17 ms 29272 KB Correct.
5 Correct 23 ms 28504 KB Correct.
6 Correct 23 ms 28764 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 29132 KB Correct.
2 Correct 40 ms 28888 KB Correct.
3 Correct 614 ms 32232 KB Correct.
4 Correct 469 ms 30480 KB Correct.
5 Correct 1148 ms 71080 KB Correct.
6 Correct 449 ms 68344 KB Correct.
7 Correct 450 ms 32336 KB Correct.
8 Correct 475 ms 30032 KB Correct.
9 Correct 236 ms 29380 KB Correct.
10 Correct 237 ms 29288 KB Correct.
11 Correct 471 ms 29776 KB Correct.
12 Correct 253 ms 29136 KB Correct.
13 Correct 265 ms 29172 KB Correct.
14 Correct 368 ms 35340 KB Correct.
15 Correct 454 ms 31344 KB Correct.
16 Correct 241 ms 29200 KB Correct.
17 Correct 294 ms 29164 KB Correct.
18 Correct 286 ms 29212 KB Correct.
19 Correct 687 ms 30032 KB Correct.
20 Correct 23 ms 28024 KB Correct.
21 Correct 22 ms 27996 KB Correct.
22 Correct 37 ms 30448 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 9560 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -