Submission #783397

# Submission time Handle Problem Language Result Execution time Memory
783397 2023-07-14T22:22:18 Z thimote75 Cyberland (APIO23_cyberland) C++17
15 / 100
32 ms 8400 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)
{
    if (reachable[node])
        return;
    reachable[node] = true;

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

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

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);
    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:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < distances.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 19 ms 412 KB Correct.
2 Correct 23 ms 468 KB Correct.
3 Correct 21 ms 464 KB Correct.
4 Correct 23 ms 460 KB Correct.
5 Correct 22 ms 468 KB Correct.
6 Correct 21 ms 1408 KB Correct.
7 Correct 25 ms 1452 KB Correct.
8 Correct 10 ms 2404 KB Correct.
9 Correct 26 ms 376 KB Correct.
10 Correct 21 ms 384 KB Correct.
# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 8400 KB Wrong Answer.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 19 ms 460 KB Correct.
2 Correct 21 ms 468 KB Correct.
3 Correct 21 ms 480 KB Correct.
4 Correct 20 ms 1444 KB Correct.
5 Correct 18 ms 364 KB Correct.
# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 432 KB Wrong Answer.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 484 KB Wrong Answer.
2 Halted 0 ms 0 KB -