Submission #1239694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239694		AlperenT_	Thousands Islands (IOI22_islands)	C++20	9.10 / 100	29 ms	28740 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
#include <bits/stdc++.h> 
//#include "segments.h"
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const int maxn = 1e6 + 10 , inf = 1e9+ 10 , mod = 998244353;
int mark[maxn] ;
vector <pii> G[maxn] ;
std::variant<bool, std::vector<int>> find_journey(int n, int m, std::vector<int> U, std::vector<int> V) {
  rep(i , 0 ,m-1){
    G[U[i]].pb({V[i] , i}); 
  }
  bool ok =0;
  vector <int> vec ;
  if(sz(G[0]) == 0)return false ;
  if(sz(G[0]) >= 2){
    vec.pb(0);
  }else{
    int v =G[0][0].F ;
    mark[0] = 1; 
    vec.pb(0) ;
    while(1){
      vec.pb(v); 
      int nx = -1;
      mark[v] = 1; 
      for(auto [u,w] : G[v]){
        if(nx!=-1 && mark[u] == 0){
          ok =1 ;
          break ;
        }
        if(mark[u] == 0)nx = u ;
      }
      if(ok == 1)break ;
      v = nx ;
      if(nx == -1)return false ;
    } 
  }
  vector <int> a , b; 
  rep(i , 0 ,sz(vec)-2){
    int v = vec[i] ;
    for(auto [u,w] : G[v]){
      if(u == vec[i+1])a.pb(w);
    }
  }
  b= a ; 
  int l = vec.back() ;
  a.pb(G[l][0].S) ;
  a.pb(G[l][0].S ^ 1); 

  a.pb(G[l][1].S) ;
  a.pb(G[l][1].S ^ 1) ;

  a.pb(G[l][0].S ^ 1);
  a.pb(G[l][0].S) ; 


  a.pb(G[l][1].S ^ 1) ;
  a.pb(G[l][0].S) ;
  reverse(all(b));
  for(int x : b)a.pb(x) ; 
  return a;
}

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