Submission #760140

#	Time	Username	Problem	Language	Result	Execution time	Memory
760140		danikoynov	Cyberland (APIO23_cyberland)	C++17	100 / 100	1259 ms	129448 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
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
    {
        ///cout << "compare " << cost << " " << div << " " << e.cost << " " << e.div << endl;
        if (div > e.div)
            return true;
        if (div < e.div)
            return false;
        return cost > e.cost;
    }
};

const int maxk = 101;
const double inf = 1e18;
const double eps = 1e-7;
vector < pair < int, ll > > 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 > 100) /// fix to 60
        K = 100;

    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, ll > nb : adj[cur])
        {
            if (!can_get[nb.first] && nb.first != H)
            {
                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)), dp[0][i] = 0;
    }

    ///for (int cnt = 0; cnt <= K)
    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, ll > nb : adj[cur.ver])
        {
            edge to(nb.first, cur.div, cur.cost + nb.second);
            ///cout << "here " << to.ver << " : " << to.cost << endl;
            if (to.cost + eps < dp[to.div][to.ver])
            {
                    ///cout << "YEP " << " ? " << endl;
                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 + eps < 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 > 1e16)
        return -1;
    return ans;
}

• 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