oj.uz

Submission #783405

# Submission time Handle Problem Language Result Execution time Memory
783405 2023-07-14T22:35:17 Z thimote75 Cyberland (APIO23_cyberland) C++17
100 / 100
 1276 ms 19396 KB 
#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;
using bdata = vector<bool>;
using ddata = vector<double>;
using idata = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using gpii = vector<vpii>;

const double INF = 1e18;

bdata reachable;

gpii roads;
idata type;

void dfs_reach(int node, int H)
{
    if (reachable[node])
        return;
    reachable[node] = true;
    if (node == H) return ;

    for (const auto &road : roads[node])
        dfs_reach(road.first, H);
}

void dijkstra(ddata &distances, int H)
{
    priority_queue<pair<double, int>> queue;
    for (int i = 0; i < distances.size(); i++)
        if (distances[i] != INF)
            queue.push({-distances[i], i});

    while (queue.size() != 0)
    {
        const auto curr = queue.top();
        queue.pop();

        double dist = -curr.first;
        int node = curr.second;

        if (node == H)
            continue;
        if (distances[node] != dist)
            continue;

        for (const auto &road : roads[node])
        {
            int next = road.first;
            double ndist = road.second + dist;
            if (ndist >= distances[next])
                continue;

            distances[next] = ndist;
            queue.push({-ndist, next});
        }
    }
}

ddata create(int N)
{
    ddata res(N, INF);
    for (int i = 0; i < N; i++)
        if (reachable[i] && type[i] == 0)
            res[i] = 0;
    return res;
}

void divide(int N, ddata &distances)
{
    ddata new_distances(N);
    for (int i = 0; i < N; i++)
        new_distances[i] = distances[i];
 
    for (int i = 0; i < N; i++)
    {
        if (!(type[i] == 2 && reachable[i]))
            continue;
 
        for (const auto &road : roads[i])
        {
            double h = (distances[i] / 2.0) + road.second;
 
            new_distances[road.first] = min(
                new_distances[road.first],
                h);
        }
    }
 
    for (int i = 0; i < N; i++)
        distances[i] = new_distances[i];
}

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)
{
    type.clear();
    type.resize(N);
    for (int i = 0; i < N; i++)
        type[i] = arr[i];
    type[0] = 0;

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

    reachable.clear();
    reachable.resize(N, false);
    dfs_reach(0, H);
    
    if (!reachable[H])
        return -1;

    ddata values = create(N);
    dijkstra(values, H);

    if (K > 70) K = 70;
    for (int i = 0; i < K; i ++) {
        divide(N, values);
        dijkstra(values, H);
    }

    return values[H];
}

Compilation message

cyberland.cpp: In function 'void dijkstra(ddata&, int)':
cyberland.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < distances.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 348 KB Correct.
2 Correct 32 ms 448 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 440 KB Correct.
2 Correct 137 ms 444 KB Correct.
3 Correct 128 ms 436 KB Correct.
4 Correct 144 ms 464 KB Correct.
5 Correct 133 ms 492 KB Correct.
6 Correct 186 ms 1816 KB Correct.
7 Correct 243 ms 1728 KB Correct.
8 Correct 106 ms 3160 KB Correct.
9 Correct 69 ms 376 KB Correct.
10 Correct 68 ms 380 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 548 KB Correct.
2 Correct 137 ms 444 KB Correct.
3 Correct 118 ms 468 KB Correct.
4 Correct 79 ms 380 KB Correct.
5 Correct 76 ms 384 KB Correct.
6 Correct 36 ms 1364 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 7024 KB Correct.
2 Correct 83 ms 496 KB Correct.
3 Correct 71 ms 552 KB Correct.
4 Correct 82 ms 464 KB Correct.
5 Correct 52 ms 392 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 552 KB Correct.
2 Correct 51 ms 456 KB Correct.
3 Correct 56 ms 476 KB Correct.
4 Correct 96 ms 1512 KB Correct.
5 Correct 34 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 472 KB Correct.
2 Correct 43 ms 464 KB Correct.
3 Correct 32 ms 7544 KB Correct.
4 Correct 63 ms 1460 KB Correct.
5 Correct 42 ms 388 KB Correct.
6 Correct 53 ms 460 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 484 KB Correct.
2 Correct 10 ms 468 KB Correct.
3 Correct 562 ms 14036 KB Correct.
4 Correct 386 ms 3368 KB Correct.
5 Correct 242 ms 8412 KB Correct.
6 Correct 83 ms 5292 KB Correct.
7 Correct 361 ms 3676 KB Correct.
8 Correct 281 ms 968 KB Correct.
9 Correct 55 ms 476 KB Correct.
10 Correct 50 ms 456 KB Correct.
11 Correct 225 ms 644 KB Correct.
12 Correct 62 ms 500 KB Correct.
13 Correct 63 ms 500 KB Correct.
14 Correct 306 ms 7164 KB Correct.
15 Correct 303 ms 2068 KB Correct.
16 Correct 64 ms 544 KB Correct.
17 Correct 73 ms 496 KB Correct.
18 Correct 63 ms 520 KB Correct.
19 Correct 212 ms 440 KB Correct.
20 Correct 4 ms 340 KB Correct.
21 Correct 4 ms 340 KB Correct.
22 Correct 7 ms 724 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 484 KB Correct.
2 Correct 19 ms 596 KB Correct.
3 Correct 1112 ms 19396 KB Correct.
4 Correct 408 ms 3260 KB Correct.
5 Correct 517 ms 10348 KB Correct.
6 Correct 158 ms 6240 KB Correct.
7 Correct 508 ms 7424 KB Correct.
8 Correct 311 ms 1968 KB Correct.
9 Correct 93 ms 1328 KB Correct.
10 Correct 98 ms 1316 KB Correct.
11 Correct 175 ms 1464 KB Correct.
12 Correct 108 ms 1448 KB Correct.
13 Correct 107 ms 1412 KB Correct.
14 Correct 962 ms 8864 KB Correct.
15 Correct 1276 ms 8220 KB Correct.
16 Correct 603 ms 3900 KB Correct.
17 Correct 381 ms 1696 KB Correct.
18 Correct 90 ms 1044 KB Correct.
19 Correct 139 ms 792 KB Correct.
20 Correct 105 ms 812 KB Correct.
21 Correct 418 ms 464 KB Correct.
22 Correct 6 ms 316 KB Correct.
23 Correct 8 ms 340 KB Correct.
24 Correct 11 ms 852 KB Correct.