Submission #1024853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024853		Svizel_pritula	Closing Time (IOI23_closing)	C++17	8 / 100	92 ms	29136 KiB

closing

#include "closing.h"

#include <bits/stdc++.h>

typedef std::int64_t i64;
typedef std::size_t usize;
typedef std::ptrdiff_t isize;

struct edge
{
    usize dest;
    i64 length;
};

struct node
{
    std::vector<edge> edges;
    i64 distance_x = std::numeric_limits<i64>::max();
    i64 distance_y = std::numeric_limits<i64>::max();

    i64 &distance(bool id)
    {
        if (id)
            return distance_y;
        else
            return distance_x;
    }
};

void mark_distances(std::vector<node> &nodes, usize start, bool id)
{
    std::queue<std::pair<i64, usize>> queue;
    queue.push({0, start});

    while (!queue.empty())
    {
        i64 dist = queue.front().first;
        usize n = queue.front().second;

        queue.pop();

        nodes[n].distance(id) = dist;

        for (edge e : nodes[n].edges)
        {
            i64 new_dist = dist + e.length;

            if (nodes[e.dest].distance(id) > dist)
                queue.push({new_dist, e.dest});
        }
    }
}

inline i64 sat_add(i64 a, i64 b)
{
    if (std::numeric_limits<i64>::max() - b < a)
        return std::numeric_limits<i64>::max();

    return a + b;
}

i64 get_best_score(std::vector<node> const &nodes, i64 max_cost)
{
    std::vector<i64> dists;

    for (node const &n : nodes)
        dists.push_back(std::min(n.distance_x, n.distance_y));

    std::sort(dists.begin(), dists.end());

    i64 cost = 0;
    usize count = 0;

    for (i64 d : dists)
    {
        cost += d;

        if (cost > max_cost)
            break;

        count++;
    }

    return count;
}

int max_score(int city_count, int city_x, int city_y, long long max_closing_sum, std::vector<int> starts, std::vector<int> ends, std::vector<int> lengths)
{
    std::vector<node> nodes(city_count);

    for (usize i = 0; i < city_count - 1; i++)
    {
        nodes[starts[i]].edges.push_back(edge{(usize)ends[i], lengths[i]});
        nodes[ends[i]].edges.push_back(edge{(usize)starts[i], lengths[i]});
    }

    mark_distances(nodes, city_x, false);
    mark_distances(nodes, city_y, true);

    return get_best_score(nodes, max_closing_sum);
}

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:91:25: warning: comparison of integer expressions of different signedness: 'usize' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |     for (usize i = 0; i < city_count - 1; i++)
      |                       ~~^~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17