Submission #1233769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233769		simplemind_31	Parachute rings (IOI12_rings)	C++20	0 / 100	229 ms	40620 KiB

rings

#include <bits/stdc++.h>
using namespace std;
int N,canticriti,asegu=-1;
vector<int> degree;
vector<bool> existeciclo;
vector<int> dsu;
vector<vector<int>> graph;
vector<int> may3;
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
void unite(int x,int y){
  if((x=find(x))==(y=find(y))){
    existeciclo[x]=true;
  }
  dsu[x]=y;
  if(existeciclo[x]){
    existeciclo[y]=true;
  }
}
void Init(int N_){
  graph.resize(canticriti=N=N_);
  degree.resize(N);
  dsu.resize(N);
  existeciclo.resize(N);
  for(int i=0;i<N;i++){
    dsu[i]=i;
  }
}
void Link(int A,int B){
  if(canticriti==0){
    return;
  }
  if(asegu!=-1){
    if(asegu!=A && asegu!=B){
      degree[A]++;
      degree[B]++;
      if(degree[A]>2 || degree[B]>2){
        canticriti=0;
      }
    }
  }else{
    unite(A,B);
    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;
      canticriti=1;
      for(auto u:graph[A]){
        degree[u]--;
      }
    }else if(degree[B]>3){
      asegu=B;
      canticriti=1;
      for(auto u:graph[B]){
        degree[u]--;
      }
    }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=i;
            break;
          }
        }
        if(asegu==-1){
          canticriti=0;
        }
        canticriti=1;
        for(auto u:graph[asegu]){
          degree[u]--;
        }
      }else if(may3.size()==2){
        canticriti=2;
      }else if(may3.size()==1){
        if(existeciclo[find(may3[0])]){
          canticriti=3;
        }else{
          canticriti=1+degree[may3[0]];
        }
      }
    }
  }
}
int CountCritical(){return canticriti;}

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