Submission #858547

#	Time	Username	Problem	Language	Result	Execution time	Memory
858547		ikura355	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	11 ms	600 KiB

longesttrip

#include "longesttrip.h"

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

std::vector<int> longest_trip(int n, int density) {
  if (density == 3) {
    // Return list of 0 to N-1
    vector<int> ans(n);
    iota(ans.begin(), ans.end(), 0);
    return ans;
  } else if (density == 2) {
    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;
  }
  return {};
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:18:15: 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