oj.uz

Submission #775235

# Submission time Handle Problem Language Result Execution time Memory
775235 2023-07-06T08:56:39 Z lollipop Parachute rings (IOI12_rings) C++17
100 / 100
 1704 ms 169108 KB 
//#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47220 KB Output is correct
2 Correct 22 ms 47960 KB Output is correct
3 Correct 26 ms 48080 KB Output is correct
4 Correct 22 ms 47316 KB Output is correct
5 Correct 21 ms 47396 KB Output is correct
6 Correct 33 ms 47544 KB Output is correct
7 Correct 21 ms 47812 KB Output is correct
8 Correct 23 ms 47472 KB Output is correct
9 Correct 23 ms 48084 KB Output is correct
10 Correct 23 ms 48000 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 80576 KB Output is correct
2 Correct 1401 ms 146856 KB Output is correct
3 Correct 1564 ms 166508 KB Output is correct
4 Correct 1030 ms 106516 KB Output is correct
5 Correct 905 ms 106556 KB Output is correct
6 Correct 839 ms 105416 KB Output is correct
7 Correct 1404 ms 164772 KB Output is correct
8 Correct 1572 ms 161856 KB Output is correct
9 Correct 1704 ms 169108 KB Output is correct
10 Correct 737 ms 104408 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47220 KB Output is correct
2 Correct 22 ms 47960 KB Output is correct
3 Correct 26 ms 48080 KB Output is correct
4 Correct 22 ms 47316 KB Output is correct
5 Correct 21 ms 47396 KB Output is correct
6 Correct 33 ms 47544 KB Output is correct
7 Correct 21 ms 47812 KB Output is correct
8 Correct 23 ms 47472 KB Output is correct
9 Correct 23 ms 48084 KB Output is correct
10 Correct 23 ms 48000 KB Output is correct
11 Correct 28 ms 48092 KB Output is correct
12 Correct 32 ms 48632 KB Output is correct
13 Correct 38 ms 48640 KB Output is correct
14 Correct 31 ms 48476 KB Output is correct
15 Correct 28 ms 49284 KB Output is correct
16 Correct 27 ms 47956 KB Output is correct
17 Correct 31 ms 48684 KB Output is correct
18 Correct 33 ms 49672 KB Output is correct
19 Correct 29 ms 47916 KB Output is correct
20 Correct 29 ms 48640 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47220 KB Output is correct
2 Correct 22 ms 47960 KB Output is correct
3 Correct 26 ms 48080 KB Output is correct
4 Correct 22 ms 47316 KB Output is correct
5 Correct 21 ms 47396 KB Output is correct
6 Correct 33 ms 47544 KB Output is correct
7 Correct 21 ms 47812 KB Output is correct
8 Correct 23 ms 47472 KB Output is correct
9 Correct 23 ms 48084 KB Output is correct
10 Correct 23 ms 48000 KB Output is correct
11 Correct 28 ms 48092 KB Output is correct
12 Correct 32 ms 48632 KB Output is correct
13 Correct 38 ms 48640 KB Output is correct
14 Correct 31 ms 48476 KB Output is correct
15 Correct 28 ms 49284 KB Output is correct
16 Correct 27 ms 47956 KB Output is correct
17 Correct 31 ms 48684 KB Output is correct
18 Correct 33 ms 49672 KB Output is correct
19 Correct 29 ms 47916 KB Output is correct
20 Correct 29 ms 48640 KB Output is correct
21 Correct 39 ms 49664 KB Output is correct
22 Correct 47 ms 51016 KB Output is correct
23 Correct 53 ms 52008 KB Output is correct
24 Correct 73 ms 57336 KB Output is correct
25 Correct 47 ms 56168 KB Output is correct
26 Correct 67 ms 58184 KB Output is correct
27 Correct 58 ms 52628 KB Output is correct
28 Correct 80 ms 58516 KB Output is correct
29 Correct 64 ms 57820 KB Output is correct
30 Correct 60 ms 53452 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47220 KB Output is correct
2 Correct 22 ms 47960 KB Output is correct
3 Correct 26 ms 48080 KB Output is correct
4 Correct 22 ms 47316 KB Output is correct
5 Correct 21 ms 47396 KB Output is correct
6 Correct 33 ms 47544 KB Output is correct
7 Correct 21 ms 47812 KB Output is correct
8 Correct 23 ms 47472 KB Output is correct
9 Correct 23 ms 48084 KB Output is correct
10 Correct 23 ms 48000 KB Output is correct
11 Correct 360 ms 80576 KB Output is correct
12 Correct 1401 ms 146856 KB Output is correct
13 Correct 1564 ms 166508 KB Output is correct
14 Correct 1030 ms 106516 KB Output is correct
15 Correct 905 ms 106556 KB Output is correct
16 Correct 839 ms 105416 KB Output is correct
17 Correct 1404 ms 164772 KB Output is correct
18 Correct 1572 ms 161856 KB Output is correct
19 Correct 1704 ms 169108 KB Output is correct
20 Correct 737 ms 104408 KB Output is correct
21 Correct 28 ms 48092 KB Output is correct
22 Correct 32 ms 48632 KB Output is correct
23 Correct 38 ms 48640 KB Output is correct
24 Correct 31 ms 48476 KB Output is correct
25 Correct 28 ms 49284 KB Output is correct
26 Correct 27 ms 47956 KB Output is correct
27 Correct 31 ms 48684 KB Output is correct
28 Correct 33 ms 49672 KB Output is correct
29 Correct 29 ms 47916 KB Output is correct
30 Correct 29 ms 48640 KB Output is correct
31 Correct 39 ms 49664 KB Output is correct
32 Correct 47 ms 51016 KB Output is correct
33 Correct 53 ms 52008 KB Output is correct
34 Correct 73 ms 57336 KB Output is correct
35 Correct 47 ms 56168 KB Output is correct
36 Correct 67 ms 58184 KB Output is correct
37 Correct 58 ms 52628 KB Output is correct
38 Correct 80 ms 58516 KB Output is correct
39 Correct 64 ms 57820 KB Output is correct
40 Correct 60 ms 53452 KB Output is correct
41 Correct 216 ms 69132 KB Output is correct
42 Correct 646 ms 139096 KB Output is correct
43 Correct 290 ms 130356 KB Output is correct
44 Correct 1210 ms 157148 KB Output is correct
45 Correct 1071 ms 155776 KB Output is correct
46 Correct 592 ms 95808 KB Output is correct
47 Correct 800 ms 96396 KB Output is correct
48 Correct 701 ms 151712 KB Output is correct
49 Correct 574 ms 98176 KB Output is correct
50 Correct 606 ms 97580 KB Output is correct
51 Correct 373 ms 121344 KB Output is correct
52 Correct 965 ms 136380 KB Output is correct
53 Correct 690 ms 151912 KB Output is correct
54 Correct 1373 ms 144576 KB Output is correct
55 Correct 1461 ms 152780 KB Output is correct