Submission #858558

#	Time	Username	Problem	Language	Result	Execution time	Memory
858558		ikura355	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	25 ms	1488 KiB

longesttrip

#include "longesttrip.h"

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

vector<int> solve3(int n) {
  vector<int> ans(n);
  iota(ans.begin(), ans.end(), 0);
  return ans;
}

vector<int> solve2(int n) {
  vector<int> nxt(n);
  int pair;
  for (int i = 1; i < n; i++)
    if (are_connected({0}, {i})) pair = i;
  int head = 0, tail = pair;
  nxt[head] = pair;
  for (int i = 0; i < n; i++) {
    if (i == 0 || i == pair) continue;
    if (are_connected({head}, {i})) {
      nxt[i] = head;
      head = i;
    } else {
      nxt[tail] = i;
      tail = i;
    }
  }
  vector<int> ans;
  while (true) {
    ans.push_back(head);
    if (head == tail) break;
    head = nxt[head];
  }
  return ans;
}

int get_connected(vector<int> x, vector<int> y) {
  if (x.empty() || y.empty()) return 0;
  return are_connected(x, y);
}

vector<int> solve1(int n) {
  vector<int> a({0}), b;
  for (int i = 1; i < n; i++) {
    int connect_a = get_connected(a, {i});
    int connect_b = get_connected(b, {i});
    if (!connect_a && !connect_b) {
      a.insert(a.end(), b.begin(), b.end());
      b = {i};
    } else {
      if (connect_b) {
        swap(a, b);
        swap(connect_a, connect_b);
      }
      // head
      if (are_connected({a[0]}, {i})) a.insert(a.begin(), i);
      // tail
      else if (are_connected({a[a.size() - 1]}, {i}))
        a.push_back(i);
      else {
        for (int j = 0; j < (int)a.size(); j++) {
          if (are_connected({a[j]}, {i})) {
            // [i] + [j, ...] + [0, ..., j-1]
            vector<int> vec;
            vec.push_back(i);
            for (int k = j; k < (int)a.size(); k++) vec.push_back(a[k]);
            for (int k = 0; k < j; k++) vec.push_back(a[k]);
            a = vec;
            break;
          }
        }
      }
      if (connect_b) {
        // connect to head
        if (are_connected({b[0]}, {i})) {
          // [bn, ..., b0] + [a0, ..., an]
          reverse(b.begin(), b.end());
          b.insert(b.end(), a.begin(), a.end());
          a = b;
          b = {};
        }
        // connect to tail
        else if (are_connected({b[b.size() - 1]}, {i})) {
          // [b0, ..., bn] + [a0, ..., an]
          b.insert(b.end(), a.begin(), a.end());
          a = b;
          b = {};
        }
        // connect to middle
        else {
          for (int j = 0; j < (int)b.size(); j++) {
            if (are_connected({b[j]}, {i})) {
              // // [bj+1, ..., bn] [b0, ..., bj] [a0, ..., an]
              vector<int> vec;
              for (int k = j + 1; k < (int)b.size(); k++) vec.push_back(b[k]);
              for (int k = 0; k <= j; k++) vec.push_back(b[k]);
              vec.insert(vec.end(), a.begin(), a.end());
              a = vec;
              b = {};
              break;
            }
          }
        }
      }
    }
  }
  if (a.size() > b.size()) return a;
  return b;
}

std::vector<int> longest_trip(int n, int density) {
  if (density == 3) return solve3(n);
  if (density == 2) return solve2(n);
  if (density == 1) return solve1(n);
  return {};
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> solve2(int)':
longesttrip.cpp:18:13: warning: 'pair' may be used uninitialized in this function [-Wmaybe-uninitialized]
   18 |   nxt[head] = pair;

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