oj.uz

답안 #827295

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
827295 2023-08-16T10:40:48 Z lollipop 수천개의 섬 (IOI22_islands) C++17
55 / 100
 37 ms 17608 KB 
#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 ;
}
        vector < short int > vi ;
void dfs( int node , int parent , int piu ){
    papiki[ node ] = piu ;
    pp[ node ] = parent ;
    col[ node ] = 2 ;
    if( tita == 1 ) return ;
    for( auto X : cur[ node ] ){
      if( tita == 1 ) return ;
      int x = vv[ X ] ;
       if( col[ x ] == 2 ){
        tita = 1 ;
        pas.pb( 1 ) ;
        int nd = node ;
        int zz = 0 ;
        make_cycle( x , node , X ) ;
        return ;
       }
       if( col[ x ] == 1 ) continue ;
       dfs( x , node , X ) ;
    }
    col[ node ] = 1 ;
}
int check1(){
   int tt  = -1 ;
   dfs( 0 , -1 , -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;
// }

Compilation message

islands.cpp: In function 'void dfs(int, int, int)':
islands.cpp:163:13: warning: unused variable 'nd' [-Wunused-variable]
  163 |         int nd = node ;
      |             ^~
islands.cpp:164:13: warning: unused variable 'zz' [-Wunused-variable]
  164 |         int zz = 0 ;
      |             ^~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 37 ms 17608 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 28 ms 16328 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 5 ms 9840 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 4 ms 9712 KB Output is correct
15 Correct 4 ms 9684 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Correct 19 ms 13560 KB Output is correct
18 Correct 17 ms 13004 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 4 ms 9684 KB Output is correct
21 Correct 4 ms 9680 KB Output is correct
22 Correct 4 ms 9684 KB Output is correct
23 Correct 28 ms 16448 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 30 ms 16868 KB Output is correct
4 Correct 32 ms 16888 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 5 ms 9876 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 5 ms 9940 KB Output is correct
11 Correct 5 ms 9940 KB Output is correct
12 Correct 5 ms 9940 KB Output is correct
13 Correct 5 ms 9940 KB Output is correct
14 Correct 5 ms 9856 KB Output is correct
15 Correct 7 ms 10000 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 5 ms 9736 KB Output is correct
18 Correct 5 ms 9876 KB Output is correct
19 Correct 5 ms 9716 KB Output is correct
20 Correct 33 ms 17288 KB Output is correct
21 Correct 31 ms 16864 KB Output is correct
22 Correct 5 ms 9812 KB Output is correct
23 Correct 4 ms 9684 KB Output is correct
24 Correct 6 ms 9684 KB Output is correct
25 Correct 5 ms 9784 KB Output is correct
26 Correct 5 ms 9944 KB Output is correct
27 Correct 33 ms 17096 KB Output is correct
28 Correct 33 ms 17112 KB Output is correct
29 Correct 4 ms 9684 KB Output is correct
30 Correct 34 ms 17408 KB Output is correct
31 Correct 4 ms 9684 KB Output is correct
32 Correct 31 ms 16732 KB Output is correct
33 Correct 31 ms 17076 KB Output is correct
34 Correct 20 ms 13560 KB Output is correct
35 Correct 5 ms 9812 KB Output is correct
36 Correct 28 ms 16328 KB Output is correct
37 Correct 32 ms 17040 KB Output is correct
38 Correct 5 ms 9684 KB Output is correct
39 Correct 28 ms 16276 KB Output is correct
40 Correct 5 ms 9812 KB Output is correct
41 Correct 34 ms 17356 KB Output is correct
42 Correct 32 ms 17072 KB Output is correct
43 Correct 4 ms 9684 KB Output is correct
44 Correct 5 ms 9812 KB Output is correct
45 Correct 5 ms 9940 KB Output is correct
46 Correct 16 ms 13004 KB Output is correct

Subtask #5
0.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 37 ms 17608 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 4 ms 9684 KB Output is correct
13 Correct 28 ms 16328 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 4 ms 9684 KB Output is correct
17 Correct 4 ms 9684 KB Output is correct
18 Correct 5 ms 9812 KB Output is correct
19 Correct 4 ms 9684 KB Output is correct
20 Correct 4 ms 9684 KB Output is correct
21 Correct 4 ms 9684 KB Output is correct
22 Correct 4 ms 9684 KB Output is correct
23 Correct 5 ms 9812 KB Output is correct
24 Correct 4 ms 9684 KB Output is correct
25 Correct 5 ms 9840 KB Output is correct
26 Correct 4 ms 9684 KB Output is correct
27 Correct 4 ms 9712 KB Output is correct
28 Correct 4 ms 9684 KB Output is correct
29 Correct 4 ms 9684 KB Output is correct
30 Correct 19 ms 13560 KB Output is correct
31 Correct 17 ms 13004 KB Output is correct
32 Correct 5 ms 9684 KB Output is correct
33 Correct 4 ms 9684 KB Output is correct
34 Correct 4 ms 9680 KB Output is correct
35 Correct 4 ms 9684 KB Output is correct
36 Correct 28 ms 16448 KB Output is correct
37 Partially correct 5 ms 9684 KB Output is partially correct
38 Correct 4 ms 9684 KB Output is correct
39 Incorrect 4 ms 9684 KB Output isn't correct
40 Halted 0 ms 0 KB -