Submission #1239708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239708		AlperenT_	Thousands Islands (IOI22_islands)	C++20	8.40 / 100	93 ms	80496 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] ;
bool ok = 0;int st[maxn] , en[maxn] ;
map <int,int> mp[maxn];int cnt =1 ;
vector <int> az ; 
void dfs(int v){
  if(ok == 1)return ;
  mark[v] = 1; 
  st[v] = cnt ; cnt++ ;
  az.pb(v);
  for(auto [u,w]: G[v]){
    if(ok == 1)break ;
    if(mark[u] == 1 && st[u] <= st[v] && en[u] == 0) {
      az.pb(u) ;
      ok =1 ;
      break ;
    }
    if(mark[u] == 1)continue ;
    dfs(u) ;
  }
  en[v] = cnt-1 ;
  if(ok == 1)return ;
  az.pop_back() ;
}

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}); 
    mp[U[i]][V[i]] = i ; 
  }
  dfs(0);
  if(sz(az) == 0)return false ;
  int id =0 ;
  vector <int> b , a ; 
  rep(i , 0 ,sz(az)-1){
    if(az[i] == az.back()){
      id = i ;
      break ;
    }
    b.pb(mp[az[i]][az[i+1]]) ;
  }
  for(int x : b)a.pb(x); 
  vector <int> vec ;
  rep(i , id, sz(az)-2){
    vec.pb(mp[az[i]][az[i+1]]) ;
  }
  for(int x : vec)a.pb(x);
  for(int x : vec)a.pb(x^1) ;
  reverse(all(vec));
  for(int x : vec)a.pb(x^1) ;
  for(int x : vec)a.pb(x);
  reverse(all(b)) ;
  for(int x : b)a.pb(x) ;;
  return a ;
}

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