oj.uz

Submission #561485

# Submission time Handle Problem Language Result Execution time Memory
561485 2022-05-12T23:51:03 Z CaroLinda Parachute rings (IOI12_rings) C++14
0 / 100
 4000 ms 71464 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 ;
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.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 40080 KB Output is correct
2 Correct 629 ms 64100 KB Output is correct
3 Execution timed out 4057 ms 71464 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 24020 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Incorrect 14 ms 23740 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 24020 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Incorrect 14 ms 23740 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 24020 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Incorrect 14 ms 23740 KB Output isn't correct
5 Halted 0 ms 0 KB -