Submission #1196144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196144		hyakup	Thousands Islands (IOI22_islands)	C++20	1.75 / 100	17 ms	4680 KiB

islands

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

vector<vector<int>> adj, v;
vector<int> pai, marc, rep;

int find( int a ){ return (( a == rep[a] ) ? a : rep[a] = find(rep[a])); }

void join( int a, int b ){
  rep[find(a)] = find(b);
}

bool dfs( int cur ){
  marc[cur] = 1;
  for( int viz : adj[cur] ){
    if( marc[viz] == 0 ){
      pai[viz] = cur;
      if( dfs( viz ) ) return true;
    }
    else if( marc[viz] == 1 ) v[viz].push_back(cur);
    else if( rep[viz] != viz ) return true; 
  }

  for( int x : v[cur] ){
    while( find(x) != 0 ){
      join( x, pai[x] );
      x = find(x);
    }
  }
  marc[cur] = 2;
  return false;
}

variant<bool, vector<int>> find_journey( int n, int m, vector<int> a, vector<int> b ){
  adj.resize(n);
  v.resize(n);
  marc.resize(n);
  pai.resize(n);
  rep.resize(n);
  iota( rep.begin(), rep.end(), 0 );
  for( int i = 0; i < m; i++ ) adj[a[i]].push_back(b[i]);


  return dfs(0);

}

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