oj.uz

Submission #884951

# Submission time Handle Problem Language Result Execution time Memory
884951 2023-12-08T17:57:47 Z RaulAndrei01 Cyberland (APIO23_cyberland) C++17
100 / 100
 1957 ms 176836 KB 
#include "cyberland.h"
#include <vector>
#include <queue>

using namespace std;
using ld = long double;
const int NMAX = 1e5;
const ld INF = 1e18;

vector<pair<int , ld> > adj[NMAX+1];
ld dist[150][NMAX+1];
vector<int> arr;
int n, m, k, h;
bool reach[NMAX+1];

void bfs ()
{
    queue<int> q;
    q.push(0);
    reach[0] = 1;
    while (q.size())
    {
        int nod = q.front();
        q.pop();
        for (auto &edg : adj[nod])
        {
            int to = edg.first;
            if (!reach[to] && to != h) {
                reach[to] = 1;
                q.push(to);
            }
        }
    }
}

void dijktra (int layer)
{
    priority_queue<pair<ld, int> , vector<pair<ld, int> > , greater<pair<ld, int> > > q;
    
    for (int i = 0; i <n; i++)
    {
        if (reach[i] && arr[i] == 0 || i == 0) {
            q.push({0.0 , i});
            dist[layer][i] = 0;
        }
    }

    if (layer > 0)
    for (int c = 1; c < n; c++)
    {
        if (arr[c] == 2 && dist[layer-1][c] != INF)
        {
            q.push({dist[layer-1][c]/2 , c});
        //    dist[layer][c] = dist[layer-1][c]/2;
        }
    }

    while (q.size())
    {
        int nod = q.top().second;
        ld crtDist = q.top().first;
        q.pop();
        if (crtDist > dist[layer][nod]) continue;
        for (auto &edg : adj[nod])
        {
            int to = edg.first;
            ld cost = edg.second;
            if (dist[layer][to] > crtDist + cost)
            {
                dist[layer][to] = crtDist + cost;
                if (to != h)
                    q.push({dist[layer][to] , to});
            }
        }
    }
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> _arr) {
    
    n = N; m = M, k = K, h = H;
    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]});
    }
    arr = _arr;
    bfs();

    for (int c = 0; c < n; c++)
    {
        dist[0][c] = INF;
    }
    dijktra(0);
    
    for (int i = 1; i <= min(K , 100); i++)
    {
        for (int c = 0; c < n; c++)
        {
            dist[i][c] = INF;
        }
        dijktra(i);
    }
    
    for (int i = 0; i < n; i++)
    {
        adj[i].clear();
        reach[i] = 0;
    }
    
    return (dist[min(K, 100)][h] != INF) ? dist[min(K, 100)][h] : -1;
}

Compilation message

cyberland.cpp: In function 'void dijktra(int)':
cyberland.cpp:42:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   42 |         if (reach[i] && arr[i] == 0 || i == 0) {
      |             ~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 50944 KB Correct.
2 Correct 38 ms 50952 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 51036 KB Correct.
2 Correct 180 ms 51024 KB Correct.
3 Correct 173 ms 51036 KB Correct.
4 Correct 185 ms 51116 KB Correct.
5 Correct 178 ms 51080 KB Correct.
6 Correct 227 ms 52308 KB Correct.
7 Correct 298 ms 52304 KB Correct.
8 Correct 131 ms 55508 KB Correct.
9 Correct 109 ms 51040 KB Correct.
10 Correct 111 ms 51328 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 51036 KB Correct.
2 Correct 211 ms 51024 KB Correct.
3 Correct 200 ms 51272 KB Correct.
4 Correct 128 ms 50888 KB Correct.
5 Correct 137 ms 50896 KB Correct.
6 Correct 61 ms 52276 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 60284 KB Correct.
2 Correct 174 ms 51276 KB Correct.
3 Correct 151 ms 51028 KB Correct.
4 Correct 164 ms 51136 KB Correct.
5 Correct 101 ms 50776 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 51268 KB Correct.
2 Correct 107 ms 51292 KB Correct.
3 Correct 119 ms 51744 KB Correct.
4 Correct 169 ms 53280 KB Correct.
5 Correct 68 ms 50780 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 51284 KB Correct.
2 Correct 97 ms 51208 KB Correct.
3 Correct 53 ms 62544 KB Correct.
4 Correct 100 ms 52764 KB Correct.
5 Correct 100 ms 50900 KB Correct.
6 Correct 115 ms 51288 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 51280 KB Correct.
2 Correct 31 ms 51284 KB Correct.
3 Correct 519 ms 44648 KB Correct.
4 Correct 329 ms 46264 KB Correct.
5 Correct 627 ms 66184 KB Correct.
6 Correct 259 ms 61944 KB Correct.
7 Correct 337 ms 52248 KB Correct.
8 Correct 277 ms 51540 KB Correct.
9 Correct 149 ms 51280 KB Correct.
10 Correct 176 ms 51372 KB Correct.
11 Correct 245 ms 51320 KB Correct.
12 Correct 168 ms 51156 KB Correct.
13 Correct 171 ms 51424 KB Correct.
14 Correct 300 ms 53208 KB Correct.
15 Correct 297 ms 52820 KB Correct.
16 Correct 156 ms 51284 KB Correct.
17 Correct 195 ms 51332 KB Correct.
18 Correct 185 ms 51412 KB Correct.
19 Correct 515 ms 51120 KB Correct.
20 Correct 14 ms 50788 KB Correct.
21 Correct 18 ms 51288 KB Correct.
22 Correct 23 ms 52060 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 162032 KB Correct.
2 Correct 92 ms 162132 KB Correct.
3 Correct 488 ms 175088 KB Correct.
4 Correct 449 ms 165032 KB Correct.
5 Correct 1957 ms 176836 KB Correct.
6 Correct 765 ms 174592 KB Correct.
7 Correct 802 ms 170316 KB Correct.
8 Correct 415 ms 164104 KB Correct.
9 Correct 431 ms 163136 KB Correct.
10 Correct 427 ms 162912 KB Correct.
11 Correct 382 ms 163132 KB Correct.
12 Correct 491 ms 163152 KB Correct.
13 Correct 466 ms 162900 KB Correct.
14 Correct 1823 ms 173968 KB Correct.
15 Correct 1562 ms 170744 KB Correct.
16 Correct 594 ms 167080 KB Correct.
17 Correct 456 ms 164272 KB Correct.
18 Correct 456 ms 163040 KB Correct.
19 Correct 606 ms 163208 KB Correct.
20 Correct 520 ms 162900 KB Correct.
21 Correct 1602 ms 163936 KB Correct.
22 Correct 40 ms 161616 KB Correct.
23 Correct 50 ms 161720 KB Correct.
24 Correct 73 ms 163356 KB Correct.