Submission #1230472

#TimeUsernameProblemLanguageResultExecution timeMemory
1230472madamadam3Thousands Islands (IOI22_islands)C++20
0 / 100
151 ms39852 KiB
#include "islands.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;

int n, m;
vi x, y;
vvi adj;

variant<bool, vi> find_journey(int N, int M, vi U, vi V) {
  n = N; m = M;
  x = U; y = V;

  map<pair<int, int>, int> edges;
  for (int i = 0; i < m; i++) {
    edges[{x[i], y[i]}]++;
  }

  bool is21 = false;
  for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      if (edges[{i, j}] >= 2 && edges[{j, i}] >= 1) is21 = true;
    }
  }
  
  if (is21) return true;
  adj.assign(n, vi());
  for (int i = 0; i < m; i+=2) {
    adj[x[i]].push_back(y[i]);
  }

  vector<bool> seen(n, false);
  queue<int> q; q.push(0);
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    seen[cur] = true;

    for (auto &v : adj[cur]) {
      if (seen[v]) return true;
      q.push(v);
    }
  }

  return false;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...