oj.uz

Submission #783403

# Submission time Handle Problem Language Result Execution time Memory
783403 2023-07-14T22:31:24 Z thimote75 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 16232 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);

    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 32 ms 468 KB Correct.
2 Correct 33 ms 752 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 444 KB Correct.
2 Correct 136 ms 436 KB Correct.
3 Correct 133 ms 484 KB Correct.
4 Correct 144 ms 444 KB Correct.
5 Correct 133 ms 452 KB Correct.
6 Correct 185 ms 1712 KB Correct.
7 Correct 245 ms 1716 KB Correct.
8 Correct 107 ms 3160 KB Correct.
9 Correct 68 ms 380 KB Correct.
10 Correct 67 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 468 KB Correct.
2 Correct 133 ms 452 KB Correct.
3 Correct 119 ms 508 KB Correct.
4 Correct 77 ms 392 KB Correct.
5 Correct 80 ms 504 KB Correct.
6 Correct 36 ms 1412 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 7024 KB Correct.
2 Correct 86 ms 1304 KB Correct.
3 Correct 71 ms 1380 KB Correct.
4 Correct 78 ms 1316 KB Correct.
5 Correct 55 ms 1248 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 468 KB Correct.
2 Correct 56 ms 464 KB Correct.
3 Correct 56 ms 488 KB Correct.
4 Correct 95 ms 1516 KB Correct.
5 Correct 34 ms 392 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 452 KB Correct.
2 Correct 43 ms 460 KB Correct.
3 Correct 32 ms 7548 KB Correct.
4 Correct 54 ms 1380 KB Correct.
5 Correct 41 ms 380 KB Correct.
6 Correct 53 ms 500 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 484 KB Correct.
2 Correct 11 ms 596 KB Correct.
3 Correct 515 ms 16232 KB Correct.
4 Correct 397 ms 5588 KB Correct.
5 Correct 239 ms 10012 KB Correct.
6 Correct 84 ms 6656 KB Correct.
7 Correct 366 ms 4856 KB Correct.
8 Correct 279 ms 2548 KB Correct.
9 Correct 55 ms 1324 KB Correct.
10 Correct 50 ms 1308 KB Correct.
11 Correct 229 ms 2492 KB Correct.
12 Correct 64 ms 1140 KB Correct.
13 Correct 61 ms 1268 KB Correct.
14 Correct 298 ms 8640 KB Correct.
15 Correct 307 ms 3988 KB Correct.
16 Correct 55 ms 1276 KB Correct.
17 Correct 75 ms 1484 KB Correct.
18 Correct 61 ms 1464 KB Correct.
19 Correct 213 ms 2328 KB Correct.
20 Correct 4 ms 340 KB Correct.
21 Correct 5 ms 424 KB Correct.
22 Correct 7 ms 852 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3069 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -