Submission #861175

#	Time	Username	Problem	Language	Result	Execution time	Memory
861175		blackslex	Cyberland (APIO23_cyberland)	C++17	100 / 100	2291 ms	136436 KiB

cyberland

#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 (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: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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 3 / 3