Submission #254342

#	Time	Username	Problem	Language	Result	Execution time	Memory
254342		oscarsierra12	Parachute rings (IOI12_rings)	C++14	0 / 100	513 ms	124496 KiB

rings

#include<bits/stdc++.h>
using namespace std ;

const int N_M = 1e6+2 ;

int N;
int dsu[N_M][6] ;
set <int> nodes ;
int degree[N_M] ;
int cnt4 = 0, cnt3 = 0 ;
int ans4 = 1, ans3 = 4 ;
vector <int> G[N_M] ;
int var[6] ; 
int indi[N_M] ;

void Init(int N_) {
  N = N_;
  for ( int i = 0 ; i <= N ; ++i ) {
     for ( int j = 0 ; j < 6 ; ++j ) dsu [i][j] = i, var[j] = 1 ;
  }
}

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 ;
   dsu[fx][d] = fy ;
   return 1 ;
}

int yet = 1, nodeE ; 

void Link(int A, int B) {
  degree[A]++ ;
  degree[B]++ ; 
  if ( degree[A] > 3 ) cnt4++, nodeE = A ;
  if ( degree[B] > 3 ) cnt4++, nodeE = B ;
  ans4 &= (cnt4 < 2) ; 
  G[A].push_back ( B ) ;
  G[B].push_back ( A ) ;
  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) ;
          }
      }
      ans4 &= uni(A,B,0) ;
      yet = 0 ;
      ans4 &= (nodes.count(nodeE)) ;
      nodes.clear() ; nodes.insert (nodeE) ;
  }
  if ( degree[B] == 3 ) swap(A,B) ;
  if ( degree[A] == 3 ) {
     if ( cnt3 == 0 ) {
         for ( auto v:G[A] ) nodes.insert (v) ;
         nodes.insert(A) ;
         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 && (min(v, i) != min(A,B)||max(v, i) != max(A,B))) var[j] &= uni(i, v, id) ;
            }
            indi[j] = id ;
            id++ ;
         }
         ans3 = nodes.size() ; 
     }
     else {
         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() ; 
     }
     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 N;
}
/*
int main() {
    Init (7) ;
    cout << CountCritical() << endl;
    Link(1, 2) ;
    cout << CountCritical() << endl;
    Link(0, 5) ;
    cout << CountCritical() << endl;
    Link(2, 0) ;
    cout << CountCritical() << endl;
    Link(3, 2) ;
    cout << CountCritical() << endl;
    Link(3, 5) ;
    cout << CountCritical() << endl;
    Link(4, 3) ;
    cout << CountCritical() << endl;
}*/

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