Submission #775235

#	Time	Username	Problem	Language	Result	Execution time	Memory
775235		lollipop	Parachute rings (IOI12_rings)	C++17	100 / 100	1704 ms	169108 KiB

rings

//#include "rings.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#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 = 1e6 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
vector < int > v[ N ] , vv[ N ] ;
int n , ss[ N ] , mx = 0 , cnt_3 = 0 , hs[ N ] ; 
int pp[ 12 ][ N ] , rk[ 12 ][ N ] , s[ 12 ][ N ] , gd[ 12 ] , mm[ 12 ][ N ] ;
int raod[ 12 ] , sm[ 12 ] ; 
vector < int > vii ; 
void cr( int node , int v ){
     s[ node ][ v ] = 1 ; 
     pp[ node ][ v ] = v ; 
     rk[ node ][ v ] = 1 ;
     return ; 
}
int find( int node , int v ){
     if( pp[ node ][ v ] == v ) return v ; 
     return pp[ node ][ v ] = find( node , pp[ node ][ v ] ) ;
}
void unite( int node , int a , int b ){
    if( rk[ node ][ a ] < rk[ node ][ b ] ) swap( a , b ) ;
    if( rk[ node ][ a ] == rk[ node ][ b ] ) rk[ node ][ a ] ++ ;
    pp[ node ][ b ] = a ; 
    s[ node ][ a ] = s[ node ][ a ] + s[ node ][ b ] ;
    return ; 
}
void add( int i , int A , int B ){
    mm[ i ][ A ] ++ , mm[ i ][ B ] ++ ;
    if( max( mm[ i ][ A ] , mm[ i ][ B ] ) >= 3 ) gd[ i ] = -1 ; 
    A = find( i , A ) ; 
    B = find( i , B ) ; 
    if( A == B ){
        raod[ i ] ++ ; 
        sm[ i ] = sm[ i ] + s[ i ][ A ] ; 
        return ; 
    }
    unite( i , A , B ) ;
}
void create( int node , int nd ){
     FOR( i , n ) cr( node , i ) ;
     FOR( i , n ){
         if( i == nd ) continue ; 
         for( auto x : vv[ i ] ){             
             if( x == nd ) continue ; 
           //  mm[ node ][ i ] ++ ; 
             if( x < i ) continue ;
             add( node , i , x ) ; 
         }
     }
}
void Init(int N){
	 n = N ; 
     vii.pb( -1 ) ; 
     create( 0 , -1 ) ; 
}
void Link(int A, int B){
     ss[ A ] ++ , ss[ B ] ++ ;
     if( ss[ A ] > 3 ){
         if( mx == 0 ){
             mx = 1 ; 
         }
     }
      if( ss[ B ] > 3 ){
         if( mx == 0 ){
             mx = 1 ; 
         }
     }    
    if( ss[ A ] == 3 && mx == 0 ){
        if( vii.size() <= 4 ){
            if( hs[ A ] == 0 ){
                hs[ A ] = 1 ; vii.pb( A ) ; 
                create( vii.size() - 1 , A ) ;
            }
            if( hs[ B ] == 0 ){
                hs[ B ] = 1 ; vii.pb( B ) ; 
                create( vii.size() - 1 , B ) ;
            }
            for( auto x : vv[ A ] ){
                if( hs[ x ] == 0 && vii.size() <= 4 ){
                    hs[ x ] = 1 ; vii.pb( x ) ;
                    create( vii.size() - 1 , x ) ;
                }
            }
        }
    }
     if( ss[ B ] == 3 && mx == 0 ){
        if( vii.size() <= 4 ){
            if( hs[ B ] == 0 ){
                hs[ B ] = 1 ; vii.pb( B ) ; 
                create( vii.size() - 1 , B ) ;
            }
            if( hs[ A ] == 0 ){
                hs[ A ] = 1 ; vii.pb( A ) ; 
                create( vii.size() - 1 , A ) ;
            }
            for( auto x : vv[ B ] ){
                if( hs[ x ] == 0 && vii.size() <= 4 ){
                    hs[ x ] = 1 ; vii.pb( x ) ;
                    create( vii.size() - 1 , x ) ;
                }
            }
        }
    }  
    FOR( i , vii.size() ) 
    if( A != vii[ i ] && B != vii[ i ] ) add( i , A , B ) ; 
    vv[ A ].pb( B ) ;
	vv[ B ].pb( A ) ;
}
int CountCritical(){
    int cnt = 0 ; 
    for( int i = 0 ; i < vii.size() ; i ++ ){
        if( i == 0 ){
            if( gd[ i ] == -1 ) continue ; 
            if( raod[ i ] == 0 ) return n ;
            if( raod[ i ] == 1 ) return sm[ i ] ;
            return 0 ; 
        }
        if( raod[ i ] != 0 ) continue ; 
        if( gd[ i ] != -1 ){
         //   cout << vii[ i ] << " " ; 
            cnt ++ ; 
        }
    }
   // cout << endl ; 
   // if( cnt == 3 ) for( auto x : vii ) cout << x << " " ; 
    return cnt ; 
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:13:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  132 |     FOR( i , vii.size() )
      |          ~~~~~~~~~~~~~~                  
rings.cpp:132:5: note: in expansion of macro 'FOR'
  132 |     FOR( i , vii.size() )
      |     ^~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:139:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for( int i = 0 ; i < vii.size() ; i ++ ){
      |                      ~~^~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31