Submission #561485

#	Time	Username	Problem	Language	Result	Execution time	Memory
561485		CaroLinda	Parachute rings (IOI12_rings)	C++14	0 / 100	4057 ms	71464 KiB

rings

#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;
bool mem ;
vector<int> adj[MAXN] ;
vector< vector<int> > grafos , dsu ;
vector<int> sumiu ;
vector<bool> melou ;
set<int> s ;

void Init(int N_) {
  N = N_;
}

int find(int idx, int x) { return (dsu[idx][x] == x) ? x : find(idx,dsu[idx][x]) ; }
void join(int idx ,int x, int y){
  x = find(idx, x) ;
  y = find(idx,y ) ;
  if(x ==y  ){
    melou[idx] = true ;
    return ;
  }
  if(rand() % 2 ) swap(x,y);
  dsu[idx][x] = y ;
}

void create(int val, int A, int B){


  sumiu.push_back(val) ;
  melou.push_back(false );
  grafos.push_back(vector<int>(N,0)) ;
  dsu.push_back(vector<int>(N)) ; iota(all(dsu.back()),0) ;

  int idx = sz(sumiu)-1;

  s.insert(val) ;

  for(int i = 0 ; i < N ; i++ ){
    if(i == val ) continue ;
    for(auto e : adj[i]){
      if(e == val ) continue ;
      if(i == A && e == B ) continue ;
      if(i == B && e == A ) continue ;
      if( (++grafos[idx][i]) > 2 ) melou[idx] = true ;
      if(i > e ) continue ;
      join(idx,i,e) ;
    }
  }


}

void Link(int A, int B) {

  //significa que jah achei alguem com 4 ou mais
  if(mem){
    for(int i = 0 ; i < sz(sumiu) ; i++ ){
      if(A == sumiu[i] || B == sumiu[i] ) continue ;
      grafos[i][A]++ ;
      grafos[i][B]++ ;
      if(grafos[i][A] > 2 || grafos[i][B] > 2 ) melou[i] = true ;
      join( i,A,B ) ;
    }
    return ;
  }

  adj[A].push_back(B) ;
  adj[B].push_back(A) ;

  if(sz(adj[B]) > sz(adj[A])) swap(A,B) ;

  if(sz(adj[A]) > 3){
    mem = true ;
    grafos.clear() ;
    sumiu.clear() ;
    melou.clear() ;
    dsu.clear() ;
    s.clear() ;
    create(A,-1,-1) ;
    return ;
  }

  for(auto &e : {A,B} ){
    if(sz(adj[e]) == 3){
      if(s.empty()){
        for(auto viz : adj[e]){
          create(viz,A,B) ;
        }
        create(e,A,B) ;
        continue ;
      }
      if(s.empty() ) mem =true ;
      sort(all(adj[e])) ;
      auto it = s.begin() ;
      while(it != s.end()){
        if(find(all(adj[e]) , *it) == adj[e].end() && *it != e ){
          for(int i = 0 ; i <sz(sumiu) ; i++ ){
            if(sumiu[i] == *it){
              swap(sumiu[i], sumiu.back()) ;
              swap(grafos[i] , grafos.back()) ;
              swap(melou[i] , melou.back()) ;
              melou.pop_back() ;
              sumiu.pop_back() ;
              grafos.pop_back() ;
            }
          }
          it = s.erase(it) ;
        }
        else it++ ;
      }
    }
  }

  for(int i = 0 ; i < sz(sumiu) ; i++ ){
      if(A == sumiu[i] || B == sumiu[i] ) continue ;
      grafos[i][A]++ ;
      grafos[i][B]++ ;
      join(i,A,B) ;
      if(grafos[i][A] > 2 || grafos[i][B] > 2 ) melou[i] = true ;
    }


}

int CountCritical() {

  if(sumiu.empty() ) return N ;

  int ans = 0 ;
  for(int i = 0 ; i < sz(melou) ; i++ )
    if(!melou[i]) ans++ ;

  return ans ;

}

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