제출 #1368335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368335		avighna	수천개의 섬 (IOI22_islands)	C++20	6.75 / 100	15 ms	5528 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) {
  if (N == 2) {
    vector<int> rig, lef;
    for (int i = 0; i < M; ++i) {
      if (U[i] == 0) {
        lef.push_back(i);
      } else {
        rig.push_back(i);
      }
    }
    if (lef.size() < 2 || rig.empty()) {
      return false;
    }
    return vector<int>({lef[0], rig[0], lef[1], lef[0], rig[0], lef[1]});
  }

  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});
      adj[V[i]].push_back({U[i], i});
    }
  }

  vector<bool> vis(M), vis_node(N);
  int cycle = 0;
  auto dfs = [&](auto &&self, int u, int edn) {
    if (edn != -1) {
      if (vis[edn]) {
        return;
      }
      vis[edn] = true;
    }
    if (vis_node[u]) {
      cycle = 1;
      return;
    }
    vis_node[u] = true;
    for (auto &[i, edc] : adj[u]) {
      if (edc == edn) { continue; }
      self(self, i, edc);
      if (cycle) {
        return;
      }
    }
  };
  dfs(dfs, 0, -1);
  if (!cycle) {
    return false;
  }
  return true;
}

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

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