oj.uz

Submission #756121

# Submission time Handle Problem Language Result Execution time Memory
756121 2023-06-11T07:18:56 Z yellowtoad Cyberland (APIO23_cyberland) C++17
100 / 100
 1646 ms 127124 KB 
#include "cyberland.h"
#include <iostream>
#include <vector>
#include <queue>
#define f first
#define s second
using namespace std;

long long n, m, k, h, arr[100010];
long double dist[75][100010], minn;
bool vis[100010];
vector<pair<int,long long>> edge[100010];
priority_queue<pair<long double,int>,vector<pair<long double,int>>,greater<pair<long double,int>>> pq;

void dfs(int u) {
    if (arr[u] == 0) dist[0][u] = 0;
    vis[u] = 1;
    for (int i = 0; i < edge[u].size(); i++) if (!vis[edge[u][i].f]) dfs(edge[u][i].f);
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> ARR) {
    n = N; m = M; k = min(K,70); h = H; minn = 1e18;
    for (int i = 0; i < n; i++) arr[i] = ARR[i];
    for (int i = 0; i < n; i++) edge[i].clear();
    for (int i = 0; i < m; i++) {
        edge[x[i]].push_back({y[i],c[i]});
        edge[y[i]].push_back({x[i],c[i]});
    }
    for (int i = 0; i <= k; i++) for (int j = 0; j < n; j++) dist[i][j] = 1e18;
    for (int i = 0; i < n; i++) vis[i] = 0;
    vis[h] = 1;
    dfs(0);
    dist[0][0] = 0;
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j < n; j++) if (dist[i][j] != 1e18) pq.push({dist[i][j],j});
        for (int i = 0; i < n; i++) vis[i] = 0;
        vis[h] = 1;
        while (pq.size()) {
            int u = pq.top().s;
            pq.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (int j = 0; j < edge[u].size(); j++) {
                if (dist[i][u]+edge[u][j].s < dist[i][edge[u][j].f]) {
                    dist[i][edge[u][j].f] = dist[i][u]+edge[u][j].s;
                    pq.push({dist[i][edge[u][j].f],edge[u][j].f});
                }
                if (arr[edge[u][j].f] == 2) dist[i+1][edge[u][j].f] = min(dist[i+1][edge[u][j].f],(dist[i][u]+edge[u][j].s)/2);
            }
        }
    }
    for (int i = 0; i <= k; i++) minn = min(minn,dist[i][h]);
    if (minn == 1e18) return -1;
    else return minn;
}

Compilation message

cyberland.cpp: In function 'void dfs(int)':
cyberland.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0; i < edge[u].size(); i++) if (!vis[edge[u][i].f]) dfs(edge[u][i].f);
      |                     ~~^~~~~~~~~~~~~~~~
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:43:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for (int j = 0; j < edge[u].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3028 KB Correct.
2 Correct 29 ms 3036 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3552 KB Correct.
2 Correct 36 ms 3484 KB Correct.
3 Correct 33 ms 3536 KB Correct.
4 Correct 35 ms 3476 KB Correct.
5 Correct 35 ms 3504 KB Correct.
6 Correct 33 ms 8616 KB Correct.
7 Correct 47 ms 8544 KB Correct.
8 Correct 24 ms 14268 KB Correct.
9 Correct 33 ms 2988 KB Correct.
10 Correct 31 ms 2984 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3484 KB Correct.
2 Correct 34 ms 3548 KB Correct.
3 Correct 32 ms 3572 KB Correct.
4 Correct 34 ms 3028 KB Correct.
5 Correct 33 ms 2984 KB Correct.
6 Correct 12 ms 7892 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 37240 KB Correct.
2 Correct 151 ms 3516 KB Correct.
3 Correct 135 ms 3512 KB Correct.
4 Correct 177 ms 3488 KB Correct.
5 Correct 91 ms 2984 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3668 KB Correct.
2 Correct 32 ms 3740 KB Correct.
3 Correct 32 ms 3636 KB Correct.
4 Correct 34 ms 9192 KB Correct.
5 Correct 29 ms 2992 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3540 KB Correct.
2 Correct 28 ms 3664 KB Correct.
3 Correct 66 ms 46664 KB Correct.
4 Correct 25 ms 7508 KB Correct.
5 Correct 33 ms 2900 KB Correct.
6 Correct 32 ms 3668 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 3552 KB Correct.
2 Correct 27 ms 4052 KB Correct.
3 Correct 768 ms 39652 KB Correct.
4 Correct 388 ms 13464 KB Correct.
5 Correct 660 ms 29340 KB Correct.
6 Correct 331 ms 14820 KB Correct.
7 Correct 396 ms 13648 KB Correct.
8 Correct 315 ms 4924 KB Correct.
9 Correct 158 ms 3788 KB Correct.
10 Correct 141 ms 3608 KB Correct.
11 Correct 272 ms 3836 KB Correct.
12 Correct 164 ms 3788 KB Correct.
13 Correct 153 ms 3684 KB Correct.
14 Correct 409 ms 17748 KB Correct.
15 Correct 344 ms 7728 KB Correct.
16 Correct 150 ms 3660 KB Correct.
17 Correct 178 ms 3600 KB Correct.
18 Correct 173 ms 3736 KB Correct.
19 Correct 474 ms 3668 KB Correct.
20 Correct 11 ms 2980 KB Correct.
21 Correct 14 ms 3420 KB Correct.
22 Correct 25 ms 4052 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 4552 KB Correct.
2 Correct 61 ms 5300 KB Correct.
3 Correct 329 ms 127124 KB Correct.
4 Correct 468 ms 9036 KB Correct.
5 Correct 1428 ms 51716 KB Correct.
6 Correct 613 ms 21464 KB Correct.
7 Correct 714 ms 29864 KB Correct.
8 Correct 375 ms 5072 KB Correct.
9 Correct 272 ms 4588 KB Correct.
10 Correct 275 ms 4676 KB Correct.
11 Correct 245 ms 3336 KB Correct.
12 Correct 314 ms 4576 KB Correct.
13 Correct 304 ms 4508 KB Correct.
14 Correct 1646 ms 52832 KB Correct.
15 Correct 1560 ms 63216 KB Correct.
16 Correct 647 ms 24144 KB Correct.
17 Correct 446 ms 7576 KB Correct.
18 Correct 316 ms 4556 KB Correct.
19 Correct 360 ms 4476 KB Correct.
20 Correct 344 ms 4564 KB Correct.
21 Correct 958 ms 4536 KB Correct.
22 Correct 21 ms 3284 KB Correct.
23 Correct 25 ms 4372 KB Correct.
24 Correct 50 ms 4948 KB Correct.