Submission #841577

#	Time	Username	Problem	Language	Result	Execution time	Memory
841577		flashmt	Longest Trip (IOI23_longesttrip)	C++17	60 / 100	781 ms	848 KiB

longesttrip

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

vector<int> longest_trip(int n, int d)
{
  if (d == 3)
  {
    vector<int> ans(n);
    iota(begin(ans), end(ans), 0);
    return ans;
  }

  vector<vector<int>> a(n, vector<int>(n));
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
      a[i][j] = a[j][i] = are_connected({i}, {j});

  auto addToPath = [&](vector<int> &path, int x)
  {
    if (a[x][path[0]]) path.insert(begin(path), x);
    else if (a[x][path.back()]) path.push_back(x);
    else
    {
      for (int i = 0; i < size(path); i++)
        if (a[x][path[i]])
        {
          rotate(begin(path), begin(path) + (i + 1), end(path));
          path.push_back(x);
          return;
        }
    }
  };

  vector<int> seen(n);
  vector<int> ans;
  for (int i = 0; i < n; i++)
    if (!seen[i])
    {
      queue<int> q;
      q.push(i);
      seen[i] = 1;
      vector<int> path = {i};
      while (!empty(q))
      {
        int x = q.front();
        q.pop();
        for (int y = 0; y < n; y++)
          if (!seen[y] && a[x][y])
          {
            seen[y] = 1;
            q.push(y);
            addToPath(path, y);
          }
      }

      if (size(path) > size(ans))
        ans = path;
    }

  return ans;
}

Compilation message (stderr)

longesttrip.cpp: In lambda function:
longesttrip.cpp:25:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |       for (int i = 0; i < size(path); i++)
      |                       ~~^~~~~~~~~~~~

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