oj.uz

Submission #1024856

# Submission time Handle Problem Language Result Execution time Memory
1024856 2024-07-16T11:15:28 Z Svizel_pritula Longest Trip (IOI23_longesttrip) C++17
5 / 100
 7 ms 428 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 5 ms 424 KB Output is correct
5 Correct 5 ms 428 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Runtime error 0 ms 344 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Runtime error 1 ms 344 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 5 ms 356 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Runtime error 0 ms 340 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -