Submission #254386

#	Time	Username	Problem	Language	Result	Execution time	Memory
254386		oscarsierra12	Parachute rings (IOI12_rings)	C++14	100 / 100	2499 ms	201748 KiB

rings

#include<bits/stdc++.h>
using namespace std ;
 
const int N_M = 1e6+2 ;
 
int N;
int dsu[N_M][10] ;
set <int> nodes ;
int degree[N_M] ;
int cnt4 = 0, cnt3 = 0 ;
int ans4 = 1, ans3 = 4, ans1 = 0 ;
vector <int> G[N_M] ;
int var[10] ; 
int indi[N_M] ;
int sz[N_M][10]; 
int tme = 0 ;

void Init(int N_) {
  N = N_;
  for ( int i = 0 ; i <= N ; ++i ) {
     nodes.insert ( i ) ;
     degree[i] = 0 ;
     indi[i] = 0 ;
     for ( int j = 0 ; j < 8 ; ++j ) dsu [i][j] = i, var[j] = 1, sz[i][j] = 1 ;
  }
  ans1 = N ;
}
 
int fnd ( int x, int d ) {
   if ( x == dsu[x][d] ) return x ;
   return dsu[x][d] = fnd ( dsu[x][d], d ) ; 
} 
 
int uni ( int x, int y, int d ) {
  // cout << "join " << x << " " << y << " " << d << endl ;
   int fx = fnd(x, d) , fy = fnd(y, d) ;
   if ( fx == fy ) return 0 ;
   sz[fy][d] += sz[fx][d] ;
   dsu[fx][d] = fy ;
   return 1 ;
}
 
int yet = 1, nodeE ; 
 
void Link(int A, int B) {
  degree[A]++ ;
  degree[B]++ ; 
  if ( degree[A] == 4 ) cnt4++, nodeE = A ;
  if ( degree[B] == 4 ) cnt4++, nodeE = B ;
  ans4 &= (cnt4 < 2) ; 
  G[A].push_back ( B ) ;
  G[B].push_back ( A ) ;
  tme += 1-uni(A,B,7) ;
  if ( tme == 1 && ans1 == N ) ans1 = sz[fnd(A,7)][7] ;
  if ( tme > 1 ) ans1 = 0 ; 
  if ( cnt4 ) {
      if ( yet ) {
          for ( int i = 0 ; i <= N ; ++i ) {
             if ( i == nodeE ) continue ;
             for ( auto v:G[i] ) if ( v > i && v != nodeE) ans4 &= uni(i, v, 0) ;
          }
          yet = 0 ;
          ans4 &= (nodes.count(nodeE)) ;
          nodes.clear() ; nodes.insert (nodeE) ;
      }
      if ( A!=nodeE && B!=nodeE ) ans4 &= uni(A,B,0) ;
  }
  if ( degree[B] == 3 ) swap(A,B) ;
  if ( degree[A] == 3 ) {
     set <int> cur ; 
     for ( auto v:G[A] ) {if ( nodes.count(v) ) cur.insert (v) ;}
     if ( nodes.count(A) ) cur.insert (A) ;
     nodes = cur ;
     ans3 = nodes.size() ; 
     if ( cnt3 == 0 ) {
        int id = 1 ;
         for ( auto j:nodes ) {
            for ( int i = 0 ; i <= N ; ++i ) {
               if ( i == j ) continue ;
               for ( auto v:G[i] ) if ( v > i && v != j && (i != min(A,B)||v != max(A,B))) var[id] &= uni(i, v, id) ;
            }
            indi[j] = id ;
            id++ ;
         }
     }
     cnt3++ ; 
  }
  if ( degree[B] == 3 ) {
     set <int> cur ; 
     for ( auto v:G[B] ) {if ( nodes.count(v) ) cur.insert (v) ;}
     if ( nodes.count(B) ) cur.insert (B) ;
     nodes = cur ;
     ans3 = nodes.size() ; 
     cnt3++ ;
  }
 // cout << A << " " << B << " " << ans3 << " " << ans4 << endl ;
  if ( cnt3 ) {
     set <int> cur ; 
     for ( auto v:nodes ) {
       //  cout << v << " " << var[indi[v]] << endl ;
         if ( v!=A && v!=B ) var[indi[v]] &= uni(A,B,indi[v]) ;
         if ( var[indi[v]] ) cur.insert ( v ) ;
     }
     nodes = cur ; 
     ans3 = nodes.size() ; 
  }
  if ( cnt4 ) ans4 &= (nodes.size()>0) ; 
}
 
int CountCritical() {
  if ( cnt4 ) return ans4 ;
  if ( cnt3 ) return ans3 ;
  return ans1;
}
/*
int main() {
   Init(7) ;
   Link(0,1) ;
   Link(0,2) ;
   Link(0,3) ;
   Link(0,4) ;
   cout << CountCritical() << endl ;
   Link(4,5) ;
      cout << CountCritical() << endl ;

   //Link(5,6) ;
      cout << CountCritical() << endl ;

   Link(6,1) ;
      cout << CountCritical() << endl ;
   Link(5,2) ;
      cout << CountCritical() << endl ;
   
}*/

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