제출 #1369229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369229		avighna	수천개의 섬 (IOI22_islands)	C++20	24 / 100	112 ms	4796 KiB

islands

#include <bits/stdc++.h>

using namespace std;

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
  vector<vector<pair<int, int>>> adj(N);
  for (int i = 0; i < M; ++i) {
    if (i % 2 == 0) {
      adj[U[i]].push_back({V[i], i});
    }
  }

  vector<bool> stk_nodes(N), vis_edges(M);
  vector<int> stk;
  int cycle = 0, start_node = -1;
  auto dfs = [&](auto &&self, int u) {
    if (stk_nodes[u]) {
      cycle = 1, start_node = u;
      return;
    }
    stk_nodes[u] = true;
    for (auto &[i, idx] : adj[u]) {
      if (vis_edges[idx]) {
        continue;
      }
      vis_edges[idx] = true;
      stk.push_back(idx);
      self(self, i);
      if (cycle) {
        return;
      }
      stk.pop_back();
    }
    stk_nodes[u] = false;
  };

  dfs(dfs, 0);
  if (!cycle) {
    return false;
  }

  vector<int> pre;
  int i = 0;
  for (; i < int(stk.size()); ++i) {
    if (U[stk[i]] == start_node) {
      break;
    }
    pre.push_back(stk[i]);
  }
  stk.erase(stk.begin(), stk.begin() + i);

  vector<int> ans = pre;
  for (int &i : stk) {
    ans.push_back(i);
  }
  for (int &i : stk) {
    ans.push_back(i + 1);
  }
  reverse(stk.begin(), stk.end());
  for (int &i : stk) {
    ans.push_back(i);
  }
  for (int &i : stk) {
    ans.push_back(i + 1);
  }
  reverse(pre.begin(), pre.end());
  for (int &i : pre) {
    ans.push_back(i);
  }
  return ans;
}

#ifdef MACOS_LOCAL
#include "grader.cpp"
#endif

• 서브태스크 1: 0 / 5
• 서브태스크 2: 0 / 5
• 서브태스크 3: 0 / 21
• 서브태스크 4: 24 / 24
• 서브태스크 5: 0 / 45