oj.uz

Submission #760140

# Submission time Handle Problem Language Result Execution time Memory
760140 2023-06-17T08:29:11 Z danikoynov Cyberland (APIO23_cyberland) C++17
100 / 100
 1259 ms 129448 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3156 KB Correct.
2 Correct 18 ms 3080 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3520 KB Correct.
2 Correct 22 ms 3492 KB Correct.
3 Correct 21 ms 3412 KB Correct.
4 Correct 27 ms 3592 KB Correct.
5 Correct 23 ms 3412 KB Correct.
6 Correct 20 ms 7536 KB Correct.
7 Correct 25 ms 7380 KB Correct.
8 Correct 14 ms 11828 KB Correct.
9 Correct 21 ms 3108 KB Correct.
10 Correct 20 ms 3080 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3488 KB Correct.
2 Correct 28 ms 3428 KB Correct.
3 Correct 20 ms 3556 KB Correct.
4 Correct 21 ms 3044 KB Correct.
5 Correct 22 ms 3096 KB Correct.
6 Correct 6 ms 6612 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 29324 KB Correct.
2 Correct 112 ms 3476 KB Correct.
3 Correct 111 ms 3420 KB Correct.
4 Correct 107 ms 3568 KB Correct.
5 Correct 70 ms 3084 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3532 KB Correct.
2 Correct 27 ms 3588 KB Correct.
3 Correct 23 ms 3540 KB Correct.
4 Correct 27 ms 7864 KB Correct.
5 Correct 18 ms 3028 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3540 KB Correct.
2 Correct 18 ms 3540 KB Correct.
3 Correct 45 ms 37144 KB Correct.
4 Correct 19 ms 6568 KB Correct.
5 Correct 24 ms 3104 KB Correct.
6 Correct 25 ms 3648 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 3576 KB Correct.
2 Correct 19 ms 3796 KB Correct.
3 Correct 374 ms 31416 KB Correct.
4 Correct 222 ms 11148 KB Correct.
5 Correct 423 ms 23476 KB Correct.
6 Correct 190 ms 13128 KB Correct.
7 Correct 220 ms 11204 KB Correct.
8 Correct 201 ms 4544 KB Correct.
9 Correct 105 ms 3564 KB Correct.
10 Correct 106 ms 3680 KB Correct.
11 Correct 182 ms 3728 KB Correct.
12 Correct 114 ms 3600 KB Correct.
13 Correct 116 ms 3532 KB Correct.
14 Correct 225 ms 14232 KB Correct.
15 Correct 204 ms 6656 KB Correct.
16 Correct 110 ms 3612 KB Correct.
17 Correct 126 ms 3560 KB Correct.
18 Correct 123 ms 3572 KB Correct.
19 Correct 327 ms 3544 KB Correct.
20 Correct 8 ms 3028 KB Correct.
21 Correct 11 ms 3412 KB Correct.
22 Correct 18 ms 3924 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 5220 KB Correct.
2 Correct 53 ms 5916 KB Correct.
3 Correct 312 ms 129448 KB Correct.
4 Correct 288 ms 9644 KB Correct.
5 Correct 1259 ms 53500 KB Correct.
6 Correct 556 ms 22272 KB Correct.
7 Correct 574 ms 30288 KB Correct.
8 Correct 315 ms 5584 KB Correct.
9 Correct 310 ms 5144 KB Correct.
10 Correct 297 ms 5184 KB Correct.
11 Correct 130 ms 3904 KB Correct.
12 Correct 351 ms 5152 KB Correct.
13 Correct 325 ms 5152 KB Correct.
14 Correct 1253 ms 54512 KB Correct.
15 Correct 1043 ms 66664 KB Correct.
16 Correct 420 ms 20660 KB Correct.
17 Correct 319 ms 8460 KB Correct.
18 Correct 316 ms 5148 KB Correct.
19 Correct 381 ms 5060 KB Correct.
20 Correct 358 ms 5044 KB Correct.
21 Correct 945 ms 5156 KB Correct.
22 Correct 17 ms 3924 KB Correct.
23 Correct 25 ms 4948 KB Correct.
24 Correct 49 ms 5460 KB Correct.