oj.uz

Submission #861175

# Submission time Handle Problem Language Result Execution time Memory
861175 2023-10-15T14:36:01 Z blackslex Cyberland (APIO23_cyberland) C++17
100 / 100
 2291 ms 136436 KB 
#include<bits/stdc++.h>
#include "cyberland.h"
#include <vector>

using namespace std;
using pid = pair<int, double>;
using tp = tuple<double, int, int, bool>;

const int N = 1e5 + 5, K = 70;
double d[N][K][2], ans = DBL_MAX;
vector<pid> v[N];
bool f[N][K][2];
priority_queue<tp, vector<tp>, greater<tp>> q;

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) {
    k = min(k, 67); ans = DBL_MAX;
    for (int i = 0; i <= n; i++) for (int j = 0; j <= k; j++) d[i][j][0] = d[i][j][1] = DBL_MAX, f[i][j][0] = f[i][j][1] = 0;
    for (int i = 0; i <= n; i++) v[i].clear();
    while (!q.empty()) q.pop();
    for (int i = 0; i < m; i++) v[x[i]].emplace_back(y[i], c[i]), v[y[i]].emplace_back(x[i], c[i]);
    for (int i = 0; i <= k; i++) for (int j = 0; j < 2; j++) d[h][i][j] = 0;
    q.emplace(d[h][0][0] = 0, h, 0, 0);
    while (!q.empty()) {
        auto [nd, nn, nk, ns] = q.top(); q.pop();
        if (f[nn][nk][ns]) continue; f[nn][nk][ns] = 1;
        for (auto &[tn, td]: v[nn]) {
            double ntd = d[nn][nk][ns] + (!ns) * (td / pow(2.00, nk));
            if (d[tn][nk][ns] > ntd) q.emplace(d[tn][nk][ns] = ntd, tn, nk, ns);
        }
        if (!arr[nn] && !ns) for (auto &[tn, td]: v[nn]) if (d[tn][nk][1] > nd) q.emplace(d[tn][nk][1] = nd, tn, nk, 1);
        if (arr[nn] == 2 && nk < k) {
            for (auto &[tn, td]: v[nn]) {
                double ntd = d[nn][nk][ns] + (!ns) * (td / pow(2.00, nk + 1));
                if (d[tn][nk + 1][ns] > ntd) q.emplace(d[tn][nk + 1][ns] = ntd, tn, nk + 1, ns);
            }
        }
    }
    for (int i = 0; i <= k; i++) for (int j = 0; j < 2; j++) ans = min(ans, d[0][i][j]);
    return (ans == DBL_MAX ? -1 : 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:25:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   25 |         if (f[nn][nk][ns]) continue; f[nn][nk][ns] = 1;
      |         ^~
cyberland.cpp:25:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   25 |         if (f[nn][nk][ns]) continue; f[nn][nk][ns] = 1;
      |                                      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4700 KB Correct.
2 Correct 19 ms 4952 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6744 KB Correct.
2 Correct 24 ms 6748 KB Correct.
3 Correct 23 ms 6744 KB Correct.
4 Correct 24 ms 6744 KB Correct.
5 Correct 25 ms 6896 KB Correct.
6 Correct 22 ms 17864 KB Correct.
7 Correct 31 ms 17952 KB Correct.
8 Correct 16 ms 33112 KB Correct.
9 Correct 22 ms 4444 KB Correct.
10 Correct 21 ms 4620 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6896 KB Correct.
2 Correct 31 ms 7772 KB Correct.
3 Correct 28 ms 7768 KB Correct.
4 Correct 29 ms 5520 KB Correct.
5 Correct 28 ms 5516 KB Correct.
6 Correct 8 ms 18012 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 81084 KB Correct.
2 Correct 411 ms 7884 KB Correct.
3 Correct 390 ms 7820 KB Correct.
4 Correct 386 ms 7764 KB Correct.
5 Correct 412 ms 5620 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 7004 KB Correct.
2 Correct 29 ms 7004 KB Correct.
3 Correct 24 ms 7004 KB Correct.
4 Correct 23 ms 18268 KB Correct.
5 Correct 23 ms 4700 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6972 KB Correct.
2 Correct 21 ms 7772 KB Correct.
3 Correct 46 ms 107392 KB Correct.
4 Correct 19 ms 16684 KB Correct.
5 Correct 25 ms 5508 KB Correct.
6 Correct 24 ms 7772 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 7144 KB Correct.
2 Correct 66 ms 9828 KB Correct.
3 Correct 1147 ms 132164 KB Correct.
4 Correct 549 ms 37632 KB Correct.
5 Correct 985 ms 71928 KB Correct.
6 Correct 499 ms 32708 KB Correct.
7 Correct 591 ms 39788 KB Correct.
8 Correct 551 ms 13372 KB Correct.
9 Correct 330 ms 7916 KB Correct.
10 Correct 295 ms 8592 KB Correct.
11 Correct 542 ms 8784 KB Correct.
12 Correct 356 ms 8188 KB Correct.
13 Correct 350 ms 8156 KB Correct.
14 Correct 489 ms 70124 KB Correct.
15 Correct 528 ms 24452 KB Correct.
16 Correct 331 ms 7980 KB Correct.
17 Correct 381 ms 8016 KB Correct.
18 Correct 327 ms 8016 KB Correct.
19 Correct 858 ms 8984 KB Correct.
20 Correct 27 ms 4696 KB Correct.
21 Correct 26 ms 7132 KB Correct.
22 Correct 49 ms 8280 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 7552 KB Correct.
2 Correct 139 ms 9808 KB Correct.
3 Correct 1414 ms 136436 KB Correct.
4 Correct 675 ms 18004 KB Correct.
5 Correct 2111 ms 83712 KB Correct.
6 Correct 1069 ms 39608 KB Correct.
7 Correct 931 ms 55904 KB Correct.
8 Correct 850 ms 10956 KB Correct.
9 Correct 699 ms 8252 KB Correct.
10 Correct 644 ms 8300 KB Correct.
11 Correct 347 ms 5716 KB Correct.
12 Correct 802 ms 8244 KB Correct.
13 Correct 736 ms 8416 KB Correct.
14 Correct 2281 ms 61440 KB Correct.
15 Correct 2291 ms 74968 KB Correct.
16 Correct 993 ms 33364 KB Correct.
17 Correct 816 ms 13332 KB Correct.
18 Correct 711 ms 8344 KB Correct.
19 Correct 830 ms 8392 KB Correct.
20 Correct 708 ms 8296 KB Correct.
21 Correct 1887 ms 9280 KB Correct.
22 Correct 56 ms 4720 KB Correct.
23 Correct 58 ms 7260 KB Correct.
24 Correct 101 ms 9176 KB Correct.