Submission #1024858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024858		Svizel_pritula	Longest Trip (IOI23_longesttrip)	C++17	40 / 100	216 ms	436 KiB

longesttrip

#include <bits/stdc++.h>

#include "longesttrip.h"

std::vector<int> longest_trip(int cities, int density)
{
    std::vector<int> path;
    path.push_back(0);

    std::vector<int> unconnected;
    for (int i = 1; i < cities; i++)
        unconnected.push_back(i);

    while (unconnected.size() > 0)
    {
        bool found = false;

        for (auto p = unconnected.begin(); p < unconnected.end(); p++)
        {
            if (are_connected({path.back()}, {*p}))
            {
                path.push_back(*p);
                unconnected.erase(p);
                found = true;
                break;
            }
        }

        if (!found)
        {
            break;
        }
    }

    if (unconnected.size() == 0)
        return path;

    int max_dist = std::min((path.size() + 1) / 2, unconnected.size());
    int join_point = -1;

    for (int dist = 0; dist <= max_dist; dist++)
    {
        int a = dist;
        int b = path.size() - dist - 1;

        if (are_connected(unconnected, {path[a]}))
        {
            join_point = a;
            break;
        }

        if (are_connected(unconnected, {path[b]}))
        {
            join_point = b;
            break;
        }
    }

    if (join_point == -1)
    {
        if (path.size() > unconnected.size())
            return path;
        else
            return unconnected;
    }

    int opposite_node = -1;

    for (int node : unconnected)
    {
        if (are_connected({node}, {path[join_point]}))
        {
            opposite_node = node;
            break;
        }
    }

    std::vector<int> result;

    if (join_point >= path.size() / 2)
    {
        for (int i = 0; i <= join_point; i++)
            result.push_back(path[i]);
    }
    else
    {
        for (int i = path.size() - 1; i >= join_point; i--)
            result.push_back(path[i]);
    }

    result.push_back(opposite_node);

    for (int node : unconnected)
        if (node != opposite_node)
            result.push_back(node);

    return result;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     if (join_point >= path.size() / 2)
      |         ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 0 / 60