oj.uz

Submission #783401

# Submission time Handle Problem Language Result Execution time Memory
783401 2023-07-14T22:30:20 Z thimote75 Cyberland (APIO23_cyberland) C++17
44 / 100
 33 ms 8952 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;
}

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);

    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
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 504 KB Correct.
2 Correct 31 ms 468 KB Correct.
3 Correct 30 ms 460 KB Correct.
4 Correct 22 ms 444 KB Correct.
5 Correct 22 ms 396 KB Correct.
6 Correct 19 ms 1364 KB Correct.
7 Correct 25 ms 1356 KB Correct.
8 Correct 11 ms 2388 KB Correct.
9 Correct 21 ms 388 KB Correct.
10 Correct 20 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 468 KB Correct.
2 Correct 24 ms 1212 KB Correct.
3 Correct 22 ms 1324 KB Correct.
4 Correct 24 ms 628 KB Correct.
5 Correct 23 ms 1188 KB Correct.
6 Correct 5 ms 1364 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 6612 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 468 KB Correct.
2 Correct 22 ms 468 KB Correct.
3 Correct 21 ms 468 KB Correct.
4 Correct 20 ms 1364 KB Correct.
5 Correct 18 ms 372 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 452 KB Correct.
2 Correct 26 ms 1236 KB Correct.
3 Correct 33 ms 8952 KB Correct.
4 Correct 14 ms 1748 KB Correct.
5 Correct 21 ms 1100 KB Correct.
6 Correct 21 ms 1012 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 492 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -