oj.uz

Submission #561488

# Submission time Handle Problem Language Result Execution time Memory
561488 2022-05-13T00:07:19 Z CaroLinda Parachute rings (IOI12_rings) C++14
0 / 100
 4000 ms 64068 KB 
#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 ;
bool suave = true ;

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;

  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){
    suave = false ;
    mem = true ;
    grafos.clear() ;
    sumiu.clear() ;
    melou.clear() ;
    dsu.clear() ;
    create(A,-1,-1) ;
    return ;
  }

  for(auto &e : {A,B} ){
    if(sz(adj[e]) == 3){
      if(sumiu.empty() && suave){
        for(auto viz : adj[e]){
          create(viz,A,B) ;
        }
        create(e,A,B) ;
        suave = false ;
        continue ;
      }
      sort(all(adj[e])) ;

      for(int i = 0 ; i <sz(sumiu) ; i++ ){
        if( find(all(adj[e]) , sumiu[i] )== adj[e].end() && sumiu[i] != e ){
            swap(sumiu[i], sumiu.back()) ;
            swap(grafos[i] , grafos.back()) ;
            swap(melou[i] , melou.back()) ;
            swap(dsu[i] , dsu.back() ) ;
            melou.pop_back() ;
            sumiu.pop_back() ;
            grafos.pop_back() ;
            i-- ;
          }
        }
      }
    }

  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(suave ) return N ;

 /* for(int i = 0 ; i < sz(sumiu) ; i++ ){
    if(sumiu[i] != 0 ) continue ;
    for(auto e : dsu[i]) cout << e << " " ;
      cout << endl ;
  } */

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

  return ans ;

}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24000 KB Output is correct
3 Correct 13 ms 24020 KB Output is correct
4 Incorrect 12 ms 23800 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 40324 KB Output is correct
2 Correct 557 ms 64068 KB Output is correct
3 Execution timed out 4067 ms 55500 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24000 KB Output is correct
3 Correct 13 ms 24020 KB Output is correct
4 Incorrect 12 ms 23800 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24000 KB Output is correct
3 Correct 13 ms 24020 KB Output is correct
4 Incorrect 12 ms 23800 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24000 KB Output is correct
3 Correct 13 ms 24020 KB Output is correct
4 Incorrect 12 ms 23800 KB Output isn't correct
5 Halted 0 ms 0 KB -