Submission #827266

#	Time	Username	Problem	Language	Result	Execution time	Memory
827266		lollipop	Thousands Islands (IOI22_islands)	C++17	31 / 100	1089 ms	21668 KiB

islands

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 1000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 4e5 + 10 ;
//mt19937 R(time(0));
map < string , int > ma , ma1 ;
#include <variant>

#include "islands.h"
 

vector < int > cur[ N ] , uu , vv , pas ; 
vector < pair < int , int > > v ; 

int n , m , been[ N ] ;
int pp[ N ] , us[ N ] ;

void make_path( int node , int par ){
    int A = node ;
    int B = vv[ cur[ node ][ 0 ] ] ;
    if( B == par ) B = vv[ cur[ node ][ 1 ] ] ;
    int D = vv[ cur[ node ] [ 0 ] ] + vv[ cur[ node ][ 1 ] ] + vv[ cur[ node ][ 2 ] ] ;
    D = D - B - par ;
    int a = -1 , b = -1 , c = -1 , d = -1 ;
    FOR( i , m ){
      if( a == -1 && uu[ i ] == A && vv[ i ] == B && us[ i ] == 0 ) a = i , us[ i ] = 1 ;
      if( b == -1 && uu[ i ] == B && vv[ i ] == A && us[ i ] == 0 ) b = i , us[ i ] = 1 ;
      if( c == -1 && uu[ i ] == A && vv[ i ] == D && us[ i ] == 0 ) c = i , us[ i ] = 1 ;
      if( d == -1 && uu[ i ] == D && vv[ i ] == A && us[ i ] == 0 ) d = i , us[ i ] = 1 ;     
     }
     if( a != -1 && b != -1 && c != -1 && d != -1 ){
        pas.pb( a ) ;
        pas.pb( b ) ;
        pas.pb( c ) ;
        pas.pb( d ) ;
        pas.pb( b ) ;
        pas.pb( a ) ;
        pas.pb( d ) ;
        pas.pb( c ) ;
     }   
}

int check(){
   int tt  = -1 ; 
   int node = 0 , par = -1 ;
   while( true ){
     pp[ node ] = par ;
     been[ node ] = 1 ;
     if( cur[ node ].size() == 1 && node != 0 ){
      return -1 ;
     }
     if( cur[ node ].size() > 2 ){
      vector < int > pip = pas ; 

      make_path( node , par ) ;

      for( int j = pip.size() - 1 ; j >= 0 ; j -- ) pas.pb( pip[ j ] ) ;
      return 1 ;
     }
     // finding next one and the path 
     int nx = vv[ cur[ node ][ 0 ] ] ;
     if( par == nx ){
       pas.pb( cur[ node ][ 1 ] ) ;
       us[ cur[ node ][ 1 ] ] = 1 ;
       nx = vv[ cur[ node ][ 1 ] ] ; 
     }
     else pas.pb( cur[ node ][ 0 ] ) , us[ cur[ node ][ 0 ] ] = 1 ; 


    //  if( been[ nx ] == 1 ){
    //   // find the cycle


    //   return 1 ;
    //  }
     par = node ;
     node = nx ;
   }

   return tt ; 
}

int col[ N ] ;
int tita = 0 ; 
int papiki[ N ] ;
vector < int > pth , axl ; 
//int pp[ N ] ;
void make_cycle( int bg , int nd , int nmb ){
    pas.clear() ;
    int BG = bg ;
    while( BG != 0 ){
      axl.pb( papiki[ BG ] ) ;
      BG = pp[ BG ] ;
    }
    // before cycle 
    reverse( axl.begin() , axl.end() ) ; 
    for( auto x : axl ) pas.pb( x ) ; 
    
    // now for cycle
    pth.pb( nmb ) ; 
    int cur = nd ; 
    while( true ){
      if( cur == -1 ) break ;
      if( cur == bg ) break ;
      pth.pb( papiki[ cur ] ) ;
      cur = pp[ cur ] ; 
    }

    reverse( pth.begin() , pth.end() ) ;
    for( auto x : pth ) pas.pb( x ) ; 
    for( auto x : pth ){
      pas.pb( x + 1 ) ; 
    }
    reverse( pth.begin() , pth.end() ) ;
    for( auto x : pth ) pas.pb( x ) ; 
    for( auto x : pth ){
      pas.pb( x + 1 ) ; 
    }   

    // after cycle
    reverse( axl.begin() , axl.end() ) ; 
    for( auto x : axl ) pas.pb( x ) ; 
    return ;
}
void dfs( int node , int parent ){
    pp[ node ] = parent ;
    col[ node ] = 2 ;
    if( tita == 1 ) return ;
    for( auto X : cur[ node ] ){
      int x = vv[ X ] ;
       if( col[ x ] == 2 ){
        tita = 1 ;
        make_cycle( x , node , X ) ;
        return ;
       }
       if( col[ x ] == 1 ) continue ;
       papiki[ x ] = X ; 
       dfs( x , node ) ;
    }
    col[ node ] = 1 ;
}
int check1(){
   int tt  = -1 ;
   dfs( 0 , -1 ) ; 
   if( tita == 1 ) tt = 1 ;
   return tt ;  
}

variant<bool, vector<int>> find_journey( int N, int M, vector<int> U, vector<int> V){
  uu = U ; vv = V ; n = N ; m = M ; 

     FOR( i , M ){
        cur[ U[ i ] ].pb( i ) ;
        v.pb( { U[ i ] , V[ i ] } ) ;
     }
     if( N == 2 ){
     if( cur[ 0 ].size() < 2 || cur[ 1 ].size() < 1 ){
      return false ;
     }
     vector < int > ans ;
     ans.pb( cur[ 0 ][ 0 ] ) ;
     ans.pb( cur[ 1 ][ 0 ] ) ;
     ans.pb( cur[ 0 ][ 1 ] ) ;
     ans.pb( cur[ 0 ][ 0 ] ) ;
     ans.pb( cur[ 1 ][ 0 ] ) ;
     ans.pb( cur[ 0 ][ 1 ] ) ; 
     return ans ;
     }

     if( cur[ 0 ].size() == 0 ) return false ;

    
     int a = -1 , b = -1 , c = -1 , d = -1 ;
     int cc1 = -1 , cc2 = -1 ; 
     cc1 = V[ cur[ 0 ][ 0 ] ] ; 
     if( cur[ 0 ].size() > 1 ){
       cc2 = V[ cur[ 0 ][ 1 ] ] ;       
     }
     FOR( i , M ){
      if( a == -1 && uu[ i ] == 0 && vv[ i ] == cc1 && us[ i ] == 0 ) a = i , us[ i ] = 1 ;
      if( b == -1 && uu[ i ] == cc1 && vv[ i ] == 0 && us[ i ] == 0 ) b = i , us[ i ] = 1 ;
      if( c == -1 && uu[ i ] == 0 && vv[ i ] == cc2 && us[ i ] == 0 ) c = i , us[ i ] = 1 ;
      if( d == -1 && uu[ i ] == cc2 && vv[ i ] == 0 && us[ i ] == 0 ) d = i , us[ i ] = 1 ;  
     }
     if( a != -1 && b != -1 && c != -1 && d != -1 ){
        vector < int > ans ;
        ans.pb( a ) ;
        ans.pb( b ) ;
        ans.pb( c ) ;
        ans.pb( d ) ;
        ans.pb( b ) ;
        ans.pb( a ) ;
        ans.pb( d ) ;
        ans.pb( c ) ;
        return ans ;
     }
    int titu = 0 ;
    if( m % 2 != 0 ) titu = -1 ;
    for( int i = 0 ; i < m ; i += 2 ){
      int cc = -1 ;
      if( U[ i ] == V[ i + 1 ] && V[ i ] == U[ i + 1 ] ) cc = 0 ;
      titu = min( titu , cc ) ;
    }
    if( titu == 0 ){
      // subtask 3 

     // sheamowme prosta xazia tuara
    int tt = check() ;
    if( tt == -1 ) return false ;
    return pas ; }
    
    pas.clear() ;
    int tt = check1() ;
    if( tt == -1 ) return false ;
    return pas ;
    

}


// int main() {
//   int N, M;
//   assert(2 == scanf("%d %d", &N, &M));

//   std::vector<int> U(M), V(M);
//   for (int i = 0; i < M; ++i) {
//     assert(2 == scanf("%d %d", &U[i], &V[i]));
//   }

//   std::variant<bool, std::vector<int>> result = find_journey(N, M, U, V);
//   if (result.index() == 0) {
//     printf("0\n");
//     if (std::get<bool>(result)) {
//       printf("1\n");
//     } else {
//       printf("0\n");
//     }
//   } else {
//     printf("1\n");
//     std::vector<int> &canoes = std::get<std::vector<int>>(result);
//     printf("%d\n", static_cast<int>(canoes.size()));
//     for (int i = 0; i < static_cast<int>(canoes.size()); ++i) {
//       if (i > 0) {
//         printf(" ");
//       }
//       printf("%d", canoes[i]);
//     }
//     printf("\n");
//   }
//   return 0;
// }

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