Submission #746359

#	Time	Username	Problem	Language	Result	Execution time	Memory
746359		math_rabbit_1028	Thousands Islands (IOI22_islands)	C++17	10.15 / 100	99 ms	21084 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>
using namespace std;

bool ans = false;

int n, m;
vector< pair<int, int> > adj[101010], rev[101010], adj2[101010], rev2[101010];
int out[101010], in[101010], remain[202020], pass[202020];

set< pair<int, int> > outset;

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
  n = N; m = M;
  for (int i = 0; i < m; i++) {
    adj[U[i]].push_back({V[i], i});
    rev[V[i]].push_back({U[i], i});
    out[U[i]]++;
    remain[i] = 1;
  }

  for (int i = 0; i < n; i++) outset.insert({out[i], i});
  while (!outset.empty() && outset.begin()->first == 0) {
    int v = outset.begin()->second;
    outset.erase(outset.begin());
    for (int i = 0; i < rev[v].size(); i++) {
      if (remain[rev[v][i].second] == 0) continue;
      remain[rev[v][i].second] = 0;
      outset.erase(outset.find(make_pair(out[rev[v][i].first], rev[v][i].first)));
      out[rev[v][i].first]--;
      outset.insert(make_pair(out[rev[v][i].first], rev[v][i].first));
    }
  }

  //for (int i = 0; i < m; i++) cout << remain[i] << "\n";
  //cout << "\n";

  for (int i = 0; i < n; i++) out[i] = in[i] = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < adj[i].size(); j++) {
      if (remain[adj[i][j].second] == 1) {
        adj2[i].push_back(adj[i][j]);
        rev2[adj[i][j].first].push_back({i, adj[i][j].second});
        in[adj[i][j].first]++;
        out[i]++;
      }
    }
  }

  if (out[0] == 1) pass[0] = 1;

  for (int i = 1; i < n; i++) {
    if (in[i] == 1 && out[i] == 1 && adj2[i][0] != rev2[i][0]) pass[i] = 1;
  }

  int v = 0;
  int t = 2000000;
  while (t--) {
    if (out[v] >= 2) {
      ans = true;
      break;
    }
    else if (out[v] == 1 && pass[v] == 1) v = adj[v][0].first;
    else break;
  }

  return ans;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i < rev[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
islands.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int j = 0; j < adj[i].size(); j++) {
      |                     ~~^~~~~~~~~~~~~~~

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