Submission #785909

#	Time	Username	Problem	Language	Result	Execution time	Memory
785909		blackslex	Cyberland (APIO23_cyberland)	C++17	15 / 100	1544 ms	109952 KiB

cyberland

#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;
const double C = 1e11;
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 : ceil(ans * C) / C);
}

Compilation message (stderr)

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:23:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   23 |         if (f[nn][nsa][nsb]) continue; f[nn][nsa][nsb] = 1;
      |         ^~
cyberland.cpp:23:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   23 |         if (f[nn][nsa][nsb]) continue; f[nn][nsa][nsb] = 1;
      |                                        ^

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3