Submission #1024856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024856		Svizel_pritula	Longest Trip (IOI23_longesttrip)	C++17	5 / 100	7 ms	428 KiB

longesttrip

#include <bits/stdc++.h>

#include "longesttrip.h"

int find_opposite(std::vector<int> set, int node)
{
    for (auto p = set.begin(); p < set.end(); p++)
    {
        if (are_connected({node}, {*p}))
        {
            return *p;
        }
    }
}

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 last_join_point = -1;

    int best_distance = std::numeric_limits<int>::max();
    int best_start = 0;
    int best_end = path.size() - 1;

    for (int i = 0; i <= path.size(); i++)
    {
        if (are_connected(unconnected, {path[i]}))
        {
            int distance = i - last_join_point - 1;

            if (distance < best_distance)
            {
                best_distance = distance;
                best_start = last_join_point;
                best_end = i;
            }

            last_join_point = i;
        }
    }

    int distance = path.size() - last_join_point - 1;

    if (distance < best_distance)
    {
        best_distance = distance;
        best_start = last_join_point;
        best_end = path.size();
    }

    int start_op = best_start == -1 ? unconnected.front() : find_opposite(unconnected, path[best_start]);
    int end_op = best_end == path.size() ? unconnected.back() : find_opposite(unconnected, path[best_end]);
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i <= path.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
longesttrip.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     int end_op = best_end == path.size() ? unconnected.back() : find_opposite(unconnected, path[best_end]);
      |                  ~~~~~~~~~^~~~~~~~~~~~~~
longesttrip.cpp:81:9: warning: unused variable 'start_op' [-Wunused-variable]
   81 |     int start_op = best_start == -1 ? unconnected.front() : find_opposite(unconnected, path[best_start]);
      |         ^~~~~~~~
longesttrip.cpp:82:9: warning: unused variable 'end_op' [-Wunused-variable]
   82 |     int end_op = best_end == path.size() ? unconnected.back() : find_opposite(unconnected, path[best_end]);
      |         ^~~~~~
longesttrip.cpp: In function 'int find_opposite(std::vector<int>, int)':
longesttrip.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
   14 | }
      | ^
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:21:22: warning: control reaches end of non-void function [-Wreturn-type]
   21 |     std::vector<int> unconnected;
      |                      ^~~~~~~~~~~

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