Submission #969006

#	Time	Username	Problem	Language	Result	Execution time	Memory
969006		sleepntsheep	Cyberland (APIO23_cyberland)	C++17	100 / 100	173 ms	67924 KiB

cyberland

#include "cyberland.h"

#include <tuple>
#include <vector>
#include <queue>
#include <utility>


#define MAX_N 100001
#define MAX_M 200001
#define MAX_K 74

int head[MAX_N], nxt[MAX_M], vv[MAX_M];

int ds[MAX_N];
int ds_find(int i){return ds[i]==i?i:(ds[i]=ds_find(ds[i]));}

double ww[MAX_M],d[MAX_N][MAX_K],p2[MAX_K];

int i = 1;
void link(int u, int v, int w)
{
    nxt[i] = head[u];
    vv[i] = v;
    ww[i] = w;
    head[u] = i++;
}

double solve(int n, int m, int kk, int h, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    for(int i=0;i<n;++i)head[i]=0,ds[i]=i;
    i=1;
    p2[0]=1;for(int j=1;j<MAX_K;++j)p2[j]=p2[j-1]/2;

    if (kk >= MAX_K) kk = MAX_K - 1;

    for (int i = 0; i < m; ++i)
    {
        if(x[i]!=h&&y[i]!=h)
        ds[ds_find(y[i])]=ds_find(x[i]); link(x[i], y[i], c[i]), link(y[i], x[i], c[i]);
    }

    for (int i = 0; i < n; ++i) for (int j = 0; j <= kk; ++j) d[i][j] = 1e18;

    arr[0]=0;
    using T = std::tuple<double, int, int>;
    std::priority_queue<T, std::vector<T>, std::greater<T> >pq;

    auto nq = [&](double cost, int u, int k) { if (cost<d[u][k])d[u][k]=cost,pq.emplace(cost,u,k); };
    nq(0,h,0);

    while (pq.size())
    {
        auto[c,u,k]=pq.top();pq.pop();
        if (d[u][k]!=c)continue;
        if(ds_find(u)==ds_find(0)&&arr[u]==0)return c;

        for(int j=head[u];j;j=nxt[j])
        {
            int v=vv[j];
            if(ds_find(v)!=ds_find(0))continue;
            double w=ww[j];

            nq(c+w*p2[k], v, k);
            if(arr[v]==2&&k<kk)
                nq(c+w*p2[k],v,k+1);
        }
    }

    return -1;
}

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:38:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   38 |         if(x[i]!=h&&y[i]!=h)
      |         ^~
cyberland.cpp:39:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   39 |         ds[ds_find(y[i])]=ds_find(x[i]); link(x[i], y[i], c[i]), link(y[i], x[i], c[i]);
      |                                          ^~~~

• 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