제출 #1074429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1074429		fv3	수천개의 섬 (IOI22_islands)	C++17	8.40 / 100	79 ms	10324 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>

using namespace std;
vector<vector<pair<int, int>>> adj;
vector<int> res, visited;
bool ok;

void DFS(int index, set<int>&path)
{
  visited[index] = 1;
  path.insert(index);

  for (auto node : adj[index])
  {
    if (path.count(node.first))
    {
      ok = true;
      return;
    }
    if (visited[node.first]) continue; 
    DFS(node.first, path);
  }
  path.erase(index);

}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) 
{
  adj = vector<vector<pair<int, int>>>(N);
  res = vector<int>();

  set<pair<int, int>> s;
  for (int i = 0; i < M; i += 2)
  {
    if (s.count({U[i], V[i]})) continue;
    adj[U[i]].push_back({V[i], i});
    s.insert({U[i], V[i]});
  }

  ok = false;
  visited = vector<int>(N);
  set<int> path;
  DFS(0, path);

  if (ok)
    return vector<int>({0});
  return false;
}

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