oj.uz

Submission #254386

# Submission time Handle Problem Language Result Execution time Memory
254386 2020-07-29T23:20:45 Z oscarsierra12 Parachute rings (IOI12_rings) C++14
100 / 100
 2499 ms 201748 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23808 KB Output is correct
2 Correct 17 ms 24576 KB Output is correct
3 Correct 19 ms 24640 KB Output is correct
4 Correct 20 ms 23936 KB Output is correct
5 Correct 16 ms 24448 KB Output is correct
6 Correct 16 ms 24704 KB Output is correct
7 Correct 17 ms 24576 KB Output is correct
8 Correct 16 ms 24576 KB Output is correct
9 Correct 18 ms 24704 KB Output is correct
10 Correct 19 ms 24704 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 109476 KB Output is correct
2 Correct 1712 ms 144304 KB Output is correct
3 Correct 1810 ms 170280 KB Output is correct
4 Correct 1614 ms 201608 KB Output is correct
5 Correct 1608 ms 201748 KB Output is correct
6 Correct 1557 ms 199240 KB Output is correct
7 Correct 1731 ms 170008 KB Output is correct
8 Correct 2310 ms 187228 KB Output is correct
9 Correct 2499 ms 200916 KB Output is correct
10 Correct 1294 ms 199696 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23808 KB Output is correct
2 Correct 17 ms 24576 KB Output is correct
3 Correct 19 ms 24640 KB Output is correct
4 Correct 20 ms 23936 KB Output is correct
5 Correct 16 ms 24448 KB Output is correct
6 Correct 16 ms 24704 KB Output is correct
7 Correct 17 ms 24576 KB Output is correct
8 Correct 16 ms 24576 KB Output is correct
9 Correct 18 ms 24704 KB Output is correct
10 Correct 19 ms 24704 KB Output is correct
11 Correct 18 ms 24704 KB Output is correct
12 Correct 22 ms 25600 KB Output is correct
13 Correct 24 ms 25600 KB Output is correct
14 Correct 20 ms 25344 KB Output is correct
15 Correct 23 ms 26624 KB Output is correct
16 Correct 21 ms 25600 KB Output is correct
17 Correct 20 ms 25472 KB Output is correct
18 Correct 24 ms 26764 KB Output is correct
19 Correct 21 ms 25600 KB Output is correct
20 Correct 23 ms 25624 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23808 KB Output is correct
2 Correct 17 ms 24576 KB Output is correct
3 Correct 19 ms 24640 KB Output is correct
4 Correct 20 ms 23936 KB Output is correct
5 Correct 16 ms 24448 KB Output is correct
6 Correct 16 ms 24704 KB Output is correct
7 Correct 17 ms 24576 KB Output is correct
8 Correct 16 ms 24576 KB Output is correct
9 Correct 18 ms 24704 KB Output is correct
10 Correct 19 ms 24704 KB Output is correct
11 Correct 18 ms 24704 KB Output is correct
12 Correct 22 ms 25600 KB Output is correct
13 Correct 24 ms 25600 KB Output is correct
14 Correct 20 ms 25344 KB Output is correct
15 Correct 23 ms 26624 KB Output is correct
16 Correct 21 ms 25600 KB Output is correct
17 Correct 20 ms 25472 KB Output is correct
18 Correct 24 ms 26764 KB Output is correct
19 Correct 21 ms 25600 KB Output is correct
20 Correct 23 ms 25624 KB Output is correct
21 Correct 48 ms 32000 KB Output is correct
22 Correct 74 ms 36748 KB Output is correct
23 Correct 93 ms 40056 KB Output is correct
24 Correct 116 ms 37112 KB Output is correct
25 Correct 54 ms 37496 KB Output is correct
26 Correct 102 ms 37624 KB Output is correct
27 Correct 102 ms 38776 KB Output is correct
28 Correct 105 ms 36856 KB Output is correct
29 Correct 91 ms 38264 KB Output is correct
30 Correct 129 ms 41208 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23808 KB Output is correct
2 Correct 17 ms 24576 KB Output is correct
3 Correct 19 ms 24640 KB Output is correct
4 Correct 20 ms 23936 KB Output is correct
5 Correct 16 ms 24448 KB Output is correct
6 Correct 16 ms 24704 KB Output is correct
7 Correct 17 ms 24576 KB Output is correct
8 Correct 16 ms 24576 KB Output is correct
9 Correct 18 ms 24704 KB Output is correct
10 Correct 19 ms 24704 KB Output is correct
11 Correct 714 ms 109476 KB Output is correct
12 Correct 1712 ms 144304 KB Output is correct
13 Correct 1810 ms 170280 KB Output is correct
14 Correct 1614 ms 201608 KB Output is correct
15 Correct 1608 ms 201748 KB Output is correct
16 Correct 1557 ms 199240 KB Output is correct
17 Correct 1731 ms 170008 KB Output is correct
18 Correct 2310 ms 187228 KB Output is correct
19 Correct 2499 ms 200916 KB Output is correct
20 Correct 1294 ms 199696 KB Output is correct
21 Correct 18 ms 24704 KB Output is correct
22 Correct 22 ms 25600 KB Output is correct
23 Correct 24 ms 25600 KB Output is correct
24 Correct 20 ms 25344 KB Output is correct
25 Correct 23 ms 26624 KB Output is correct
26 Correct 21 ms 25600 KB Output is correct
27 Correct 20 ms 25472 KB Output is correct
28 Correct 24 ms 26764 KB Output is correct
29 Correct 21 ms 25600 KB Output is correct
30 Correct 23 ms 25624 KB Output is correct
31 Correct 48 ms 32000 KB Output is correct
32 Correct 74 ms 36748 KB Output is correct
33 Correct 93 ms 40056 KB Output is correct
34 Correct 116 ms 37112 KB Output is correct
35 Correct 54 ms 37496 KB Output is correct
36 Correct 102 ms 37624 KB Output is correct
37 Correct 102 ms 38776 KB Output is correct
38 Correct 105 ms 36856 KB Output is correct
39 Correct 91 ms 38264 KB Output is correct
40 Correct 129 ms 41208 KB Output is correct
41 Correct 409 ms 102448 KB Output is correct
42 Correct 1212 ms 154872 KB Output is correct
43 Correct 564 ms 152056 KB Output is correct
44 Correct 1234 ms 159352 KB Output is correct
45 Correct 1402 ms 167288 KB Output is correct
46 Correct 1174 ms 170412 KB Output is correct
47 Correct 1486 ms 173296 KB Output is correct
48 Correct 922 ms 165556 KB Output is correct
49 Correct 1233 ms 192888 KB Output is correct
50 Correct 1224 ms 190648 KB Output is correct
51 Correct 573 ms 134136 KB Output is correct
52 Correct 1006 ms 132600 KB Output is correct
53 Correct 945 ms 164616 KB Output is correct
54 Correct 2187 ms 161272 KB Output is correct
55 Correct 1605 ms 153976 KB Output is correct