Submission #760124

#	Time	Username	Problem	Language	Result	Execution time	Memory
760124		danikoynov	사이버랜드 (APIO23_cyberland)	C++17	15 / 100	529 ms	37220 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];

int can_get[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(), can_get[i] = 0;
    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]});
    }


    queue < int > tmp;
    tmp.push(0);
    can_get[0] = 1;
    while(!tmp.empty())
    {
        int cur = tmp.front();
        tmp.pop();
        for (pair < int, double > nb : adj[cur])
        {
            if (!can_get[nb.first])
            {
                can_get[nb.first] = 1;
                tmp.push(nb.first);
            }
        }
    }

    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));

    for (int i = 0; i < N; i ++)
    {
        if (can_get[i] && arr[i] == 0)
            q.push(edge(i, 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 (to.cost < dp[to.div][to.ver])
            {
                dp[to.div][to.ver] = to.cost;
                q.push(to);
            }
            if (arr[to.ver] == 2 && 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;
}

• 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