oj.uz

Submission #783388

# Submission time Handle Problem Language Result Execution time Memory
783388 2023-07-14T22:17:28 Z thimote75 Cyberland (APIO23_cyberland) C++17
0 / 100
 22 ms 5708 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;

gpii roads;

void dijkstra (ddata &distances) {
    priority_queue<pair<double, int>> pq;
    for (int i = 0; i < distances.size(); i ++)
        if (distances[i] != INF)
            pq.push({ - distances[i], i });
    
    while (pq.size() != 0) {
        const auto curr = pq.top(); pq.pop();

        auto dist = - curr.first;
        auto node = curr.second;
        if (dist != distances[node]) continue ;

        for (const auto &road : roads[node]) {
            int next = road.first;
            int cost = road.second + dist;

            if (cost >= distances[next]) continue ;

            distances[next] = cost;
            pq.push({ - cost, next });
        }
    }
}

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) {
    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] });
    }

    ddata distances(N, INF);
    distances[0] = 0;
    dijkstra(distances);

    if (distances[H] == INF) return -1;
    return distances[H];
}

Compilation message

cyberland.cpp: In function 'void dijkstra(ddata&)':
cyberland.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     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
0.0 / 8.0

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

Subtask #3
0.0 / 13.0

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

Subtask #4
0.0 / 19.0

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

Subtask #5
0.0 / 7.0

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

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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