Submission #562478

#	Time	Username	Problem	Language	Result	Execution time	Memory
562478		CaroLinda	Parachute rings (IOI12_rings)	C++14	55 / 100	4062 ms	80264 KiB

rings

/*
SUBTASK 1 JUST TO TEST HIPHOTESES
*/

#include <bits/stdc++.h>
 
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
 
const int MAXN = 1e6+10 ;
 
using namespace std ;
 
int N ;
vector<int> adj[MAXN] ;
 
int disappear(int x){
  //if x != -1, then I already removed someone and I can not have cycles/degree 3
  //if x == -1, I can have a SINGLE cycle and the answer will be the size of cycle
  //in every case, nobody can have degree three

  vector<int> dsu(N) ; iota(all(dsu) , 0 ) ;
  vector<int> qtd(N,1) ;
  vector<int> deg(N,0) ;
  int qtdCycle = 0 , sz_cycle = N ;

  function<int(int)> find = [&](int a){

    return dsu[a] = (a == dsu[a]) ? a : find(dsu[a]) ;

  } ;

  auto isCycle = [&](int a, int b){

    a = find(a) ;
    b = find(b) ;

    if(a == b ) return true ;

    if(rand() % 2 ) swap(a,b) ;
    dsu[a] = b ;
    qtd[b] += qtd[a] ;

    return false ;

  } ;

  for(int i = 0 ; i < N;  i++ ){
    if(i == x ) continue ;
    for(auto neigh : adj[i]){
      if(neigh == x ) continue ;
      if((++deg[i]) > 2 ) return 0 ;
      if(i < neigh){
        if(isCycle(i,neigh)){
          qtdCycle++ ;
          sz_cycle = qtd[find(i)] ;
        }
      }
    }
  }

  if(x != -1 ) return qtdCycle == 0 ;
  return qtdCycle <= 1 ? sz_cycle : 0 ;

}

void Init(int N_) {
  N = N_;
}
 
void Link(int A, int B) {
  adj[A].push_back(B) ;
  adj[B].push_back(A) ;
}
 
int CountCritical() {

  int ans = disappear(-1) ;

  for(int i = 0 ; i < N ; i++ ){
    if( sz(adj[i]) >= 3 ){
      ans += disappear(i) ;
      for(int j = 0 ; j < 3 ; j++ )
        ans += disappear(adj[i][j]) ;
      return ans ;
    }
  }

  return ans ;

}

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