Submission #996297

#	Time	Username	Problem	Language	Result	Execution time	Memory
996297		kunzaZa183	Longest Trip (IOI23_longesttrip)	C++17	30 / 100	26 ms	600 KiB

longesttrip

#include "longesttrip.h"

#include <bits/stdc++.h>
using namespace std;

vector<int> longest_trip(int N, int D) {
  vector<int> trip1(1, 0), trip2;
  for (int i = 1; i < N; i++) {
    bool b = are_connected(vector<int>(1, trip1.front()), vector<int>(1, i)),
         b2 = are_connected(vector<int>(1, trip1.back()), vector<int>(1, i));
    if (!b && !b2)
      trip2.push_back(i);
    else if (trip2.empty()) {
      if (b)
        trip1.insert(trip1.begin(), i);
      else
        trip2.push_back(i);
    } else if (b) {
      bool b3 = are_connected(vector<int>(1, trip2.front()), vector<int>(1, i)),
           b4 = are_connected(vector<int>(1, trip2.back()), vector<int>(1, i));
      if (b3) {
        trip1.insert(trip1.begin(), i);
        for (auto a : trip2) trip1.insert(trip1.begin(), a);
        trip2.clear();
      } else if (b4) {
        trip2.push_back(i);
        for (auto a : trip1) trip2.push_back(a);
        trip1 = trip2;
        trip2.clear();
      } else {
        trip1.insert(trip1.begin(), i);
      }
    } else if (b2) {
      bool b3 = are_connected(vector<int>(1, trip2.front()), vector<int>(1, i)),
           b4 = are_connected(vector<int>(1, trip2.back()), vector<int>(1, i));
      if (b3) {
        trip1.push_back(i);
        for (auto a : trip2) trip1.push_back(a);
        trip2.clear();
      } else if (b4) {
        reverse(trip2.begin(), trip2.end());
        trip1.push_back(i);
        for (auto a : trip2) trip1.push_back(a);
        trip2.clear();
      } else {
        trip1.push_back(i);
      }
    }
  }
  if (trip1.size() < trip2.size()) trip1.swap(trip2);
  return trip1;
}

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