oj.uz

Submission #785910

# Submission time Handle Problem Language Result Execution time Memory
785910 2023-07-17T18:44:26 Z blackslex Cyberland (APIO23_cyberland) C++17
15 / 100
 1492 ms 108944 KB 
#include<bits/stdc++.h>
#include "cyberland.h"

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

const int N = 1e5 + 5, K = 75;
double d[N][K][2], ans;
vector<pid> v[N];
bool f[N][K][2];

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 = 1e11;
    priority_queue<tp, vector<tp>, greater<tp>> q;
    for (int i = 0; i <= n; i++) v[i].clear();
    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 <= n; i++) for (int j = 0; j <= k; j++) d[i][j][0] = d[i][j][1] = 1e11, f[i][j][0] = f[i][j][1] = 0;
    q.emplace(d[h][0][0] = 0, h, 0, 0);
    while (!q.empty()) {
        auto [nd, nn, nsa, nsb] = q.top(); q.pop();
        if (f[nn][nsa][nsb]) continue; f[nn][nsa][nsb] = 1;
        for (auto &[tn, td]: v[nn]) {
            double nds = nd + (nsb ? 0 : td / pow((double) 2, nsa));
            if (d[tn][nsa][nsb] > nds) q.emplace(d[tn][nsa][nsb] = nds, tn, nsa, nsb);
        }
        if (!arr[nn]) for (auto &[tn, td]: v[nn]) if (d[tn][nsa][!nsb] > nd) q.emplace(d[tn][nsa][!nsb] = nd, tn, nsa, !nsb);
        if (nsa < k && arr[nn] == 2) {
            for (auto &[tn, td]: v[nn]) {
                double nds = nd + (nsb ? 0 : td / pow((double) 2, nsa + 1));
                if (d[tn][nsa][nsb] > nds) q.emplace(d[tn][nsa][nsb] = nds, tn, nsa + 1, nsb);
            }
        }
    }
    for (int i = 0; i <= k; i++) for (int j = 0; j < 2; j++) ans = min(ans, d[0][i][j]);
    return (ans == 1e11 ? -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:22:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   22 |         if (f[nn][nsa][nsb]) continue; f[nn][nsa][nsb] = 1;
      |         ^~
cyberland.cpp:22:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   22 |         if (f[nn][nsa][nsb]) continue; f[nn][nsa][nsb] = 1;
      |                                        ^

Subtask #1
0.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4100 KB Correct.
2 Correct 25 ms 4104 KB Correct.
3 Correct 24 ms 4120 KB Correct.
4 Correct 27 ms 4160 KB Correct.
5 Correct 29 ms 4152 KB Correct.
6 Correct 30 ms 16452 KB Correct.
7 Correct 37 ms 16308 KB Correct.
8 Correct 25 ms 30164 KB Correct.
9 Correct 23 ms 2876 KB Correct.
10 Correct 22 ms 2772 KB Correct.

Subtask #3
0.0 / 13.0

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

Subtask #4
0.0 / 19.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4268 KB Correct.
2 Correct 24 ms 4272 KB Correct.
3 Correct 22 ms 4252 KB Correct.
4 Correct 31 ms 16800 KB Correct.
5 Correct 19 ms 2772 KB Correct.

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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