Submission #783405

#	Time	Username	Problem	Language	Result	Execution time	Memory
783405		thimote75	Cyberland (APIO23_cyberland)	C++17	100 / 100	1276 ms	19396 KiB

cyberland

#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 (stderr)

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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 3 / 3