Submission #760121

#	Time	Username	Problem	Language	Result	Execution time	Memory
760121		danikoynov	Cyberland (APIO23_cyberland)	C++17	20 / 100	208 ms	29064 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;

struct edge
{
    int ver, div;
    double cost;

    edge(int _ver = 0, int _div = 0, double _cost = 0)
    {
        ver = _ver;
        div = _div;
        cost = _cost;
    }

    bool operator < (const edge &e) const
    {
        if (div > e.div)
            return true;
        return cost > e.cost;
    }
};

const int maxk = 31;
const double inf = 1e18;

vector < pair < int, double > > adj[maxn];

double dp[maxk][maxn];
int used[maxk][maxn];
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
    if (K > 30)
        K = 30;

        for (int i = 0; i < N; i ++)
            adj[i].clear();
    for (int i = 0; i < M; i ++)
    {
        adj[x[i]].push_back({y[i], c[i]});
        adj[y[i]].push_back({x[i], c[i]});
    }

    priority_queue < edge > q;
    for (int j = 0; j <= K; j ++)
        for (int i = 0; i < N; i ++)
        {
            used[j][i] = 0;
            dp[j][i] = inf;
        }

    dp[0][0] = 0;
    q.push(edge(0, 0, 0));
    while(!q.empty())
    {
        edge cur = q.top();
        q.pop();
        ///cout << q.size() << endl;
        ///cout << cur.ver << " " << cur.div << " " << cur.cost << endl;
        //cout << used[cur.div][cur.ver] << endl;
        if (used[cur.div][cur.ver])
            continue;

        used[cur.div][cur.ver] = 1;
        if (cur.ver == H)
            continue;
        ///cout << adj[cur.ver].size() << endl;
        for (pair < int, double > nb : adj[cur.ver])
        {
            edge to(nb.first, cur.div, cur.cost + nb.second);
            ///cout << "here " << to.ver << " : " << to.cost << endl;
            if (arr[to.ver] == 0)
            {
                to.cost = 0;
                if (to.cost < dp[to.div][to.ver])
                {
                    dp[to.div][to.ver] = to.cost;
                    q.push(to);
                }
            }
            else if (arr[to.ver] == 1)
            {
                if (to.cost < dp[to.div][to.ver])
                {
                    dp[to.div][to.ver] = to.cost;
                    q.push(to);
                }
            }
            else
            {
                if (to.cost < dp[to.div][to.ver])
                {
                    dp[to.div][to.ver] = to.cost;
                    q.push(to);
                }
                if (to.div < K)
                {

                    to.cost = to.cost / 2.0;
                    to.div ++;
                    if (to.cost < dp[to.div][to.ver])
                    {
                        dp[to.div][to.ver] = to.cost;
                        q.push(to);
                    }
                }
            }
        }
    }

    double ans = inf;
    for (int j = 0; j <= K; j ++)
        ans = min(ans, dp[j][H]);
        if (ans == inf)
            return -1;
    return 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:38:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   38 |     if (K > 30)
      |     ^~
cyberland.cpp:41:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   41 |         for (int i = 0; i < N; i ++)
      |         ^~~
cyberland.cpp:117:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  117 |     for (int j = 0; j <= K; j ++)
      |     ^~~
cyberland.cpp:119:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  119 |         if (ans == inf)
      |         ^~

• Subtask 1: 5 / 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