제출 #1234486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234486		simplemind_31	낙하산 고리들 (IOI12_rings)	C++20	0 / 100	1137 ms	137516 KiB

rings

#include <bits/stdc++.h>
using namespace std;
int N,canticriti,asegu=-1,canticiclo,ideal,contaaa;
vector<int> degree;
vector<int> dsu;
vector<vector<int>> graph;
vector<int> may3;
set<pair<int,int>> unidos;
vector<bool> pertenececiclo;
int target=-1;
bool dfs(int now,int ante){
  if(pertenececiclo[now]){
    return false;
  }
  if(now==target){
    contaaa++;
    return pertenececiclo[now]=true;
  }
  for(auto u:graph[now]){
    if(u==ante){
      continue;
    }
    if(dfs(u,now)){
      contaaa++;
      return pertenececiclo[now]=true;
    }
  }
  return false;
}
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
bool unite(int x,int y){
  if((x=find(x))==(y=find(y))){
    return false;
  }
  dsu[x]=y;
  return true;
}
void Init(int N_){
  graph.clear();
  degree.clear();
  dsu.clear();
  pertenececiclo.clear();
  may3.clear();
  canticiclo=ideal=contaaa=0;
  graph.resize(canticriti=N=N_);
  degree.resize(N);
  dsu.resize(N);
  pertenececiclo.assign(N,false);
  for(int i=0;i<N;i++){
    dsu[i]=i;
  }
}
void reinicar(){
  Init(N);
  for(auto u:unidos){
    if(u.first==asegu || u.second==asegu){
      continue;
    }
    degree[u.first]++;
    degree[u.second]++;
    graph[u.first].push_back(u.second);
    graph[u.second].push_back(u.first);
    if(degree[u.first]>2 || degree[u.second]>2 || !unite(u.first,u.second)){
      canticriti=0;
      return;
    }
  }
  canticriti=1;
}
void Link(int A,int B){
  if(canticriti==0){
    return;
  }
  //nuevo variante=ciclos
  // si existe 2 ciclos entonces canti=0
  // si existe 1 ciclo critic ring debe estar dentro del ciclo
  if(asegu!=-1){
    // al encontrar asegu inicio de nuevo pero olvidandome del asegu, es decir nunca unir asegu
    if(asegu!=A && asegu!=B){
      degree[A]++;
      degree[B]++;
      graph[A].push_back(B);
      graph[B].push_back(A);
      //si encuentro ciclo entonces canti=0;
      if(degree[A]>2 || degree[B]>2 || !unite(A,B)){
        canticriti=0;
        return;
      }
    }
  }else{
    unidos.insert({min(A,B),max(A,B)});
    if(!unite(A,B)){
      target=B;
      ideal++;
      if(dfs(A,B)){
        canticiclo++;
        if(canticiclo>1){
          canticriti=0;
          return;
        }
      }
    }
    degree[A]++;
    degree[B]++;
    graph[A].push_back(B);
    graph[B].push_back(A);
    if(degree[A]>3 && degree[B]>3){
      canticriti=0;
    }else if(degree[A]>3){
      asegu=A;
      reinicar();
    }else if(degree[B]>3){
      asegu=B;
      reinicar();
    }else{
      if(degree[A]==3){
        may3.push_back(A);
      }
      if(degree[B]==3){
        may3.push_back(B);
      }
      if(may3.size()>2){
        //buscar al asegu
        sort(may3.begin(),may3.end());
        for(int i=0;i<may3.size();i++){
          int con=0;
          for(auto u:graph[may3[i]]){
            if(binary_search(may3.begin(),may3.end(),u)){
              con++;
            }
          }
          if(con==may3.size()-1){
            asegu=may3[i];
            break;
          }
        }
        if(asegu==-1){
          canticriti=0;
          return;
        }else{
          reinicar();
        }
      }else if(may3.size()==2){
        if(unidos.find({min(may3[0],may3[1]),max(may3[0],may3[1])})==unidos.end()){
          canticriti=0;
          return;
        }
        if(canticiclo==1){
          if(pertenececiclo[may3[0]] && pertenececiclo[may3[1]]){
            canticriti=2;
            return;
          }else if(pertenececiclo[may3[0]] || pertenececiclo[may3[1]]){
            canticriti=1;
            return;
          }else{
            canticriti=0;
            return;
          }
        }else{
          canticriti=2;
          return;
        }
      }else if(may3.size()==1){
        if(canticiclo==1){
          if(pertenececiclo[may3[0]]){
            canticriti=3;
            return;
          }else{
            canticriti=0;
            return;
          }
        }else{
          canticriti=1+degree[may3[0]];
        }
      }else{
        if(canticiclo==1){
          canticriti=contaaa;
          return;
        }else{
          //no pasa nada
        }
      }
    }
  }
}
int CountCritical(){return canticriti;}

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