Submission #787562

#	Time	Username	Problem	Language	Result	Execution time	Memory
787562		thimote75	Thousands Islands (IOI22_islands)	C++17	8.40 / 100	33 ms	6336 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;
using bdata = vector<bool>;

igrid roads;

bdata visited;
bdata visiting;
idata path;

bool dfs (int node) {
  if (visiting[node]) {
    path.push_back(node);
    return true;
  }
  if (visited[node]) return false;
  path.push_back(node);
  visited[node] = true;
  visiting[node] = true;

  for (int next : roads[node]) if (dfs(next))
    return true;

  visiting[node] = false;
  path.pop_back();
  return false;
}

std::variant<bool, idata> find_journey(
    int N, int M, idata U, idata V) {
  roads.resize(N);
  visited.resize(N); visiting.resize(N);
  bool st3 = M % 2 == 0;
  for (int i = 0; i < M; i ++)
    roads[U[i]].push_back(V[i]);
  for (int i = 0; i + 1 < M; i += 2)
    st3 &= (U[i] == U[i + 1]) && (V[i] == V[i + 1]);
  
  if (!dfs(0)) return false;

  idata dpath;
  idata cycle;
  int joint = path[path.size() - 1];

  bool f_joint = false;
  for (int i = 0; i + 1 < path.size(); i ++) {
    if (f_joint) cycle.push_back(path[i]);
    else if (path[i] != joint) dpath.push_back(path[i]);

    f_joint |= path[i] == joint;
  }

  idata answer;
  if (st3) { // dpath + (joint + cycle) * 2 + (joint + cycle^-1) * 2 + joint + dpath^-1
    for (int u : dpath) answer.push_back(u);
    answer.push_back(joint);
    for (int u : cycle) answer.push_back(u);
    answer.push_back(joint);
    for (int u : cycle) answer.push_back(u);
    reverse(cycle.begin(), cycle.end());
    answer.push_back(joint);
    for (int u : cycle) answer.push_back(u);
    answer.push_back(joint);
    for (int u : cycle) answer.push_back(u);
    answer.push_back(joint);
    reverse(dpath.begin(), dpath.end());
    for (int u : dpath) answer.push_back(u);
  }

  return answer;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 21
• Subtask 4: 8.399999999999999 / 24
• Subtask 5: 0 / 45