Submission #1024853

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1024853	2024-07-16T11:10:49 Z	Svizel_pritula	Closing Time (IOI23_closing)	C++17	8 / 100	92 ms	29136 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	25544 KB	Output is correct
2	Correct	92 ms	29136 KB	Output is correct
3	Correct	61 ms	5456 KB	Output is correct

Subtask #2
0.0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '30', found: '17'
3	Halted	0 KB	-

Subtask #3
0.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '30', found: '17'
3	Halted	0 KB	-

Subtask #4
0.0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	1st lines differ - on the 1st token, expected: '30', found: '17'
3	Halted	0 KB	-

Subtask #5
0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-