제출 #1233766

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

rings

#include <bits/stdc++.h>
using namespace std;
int N,canticriti,asegu=-1;
vector<int> degree;
vector<vector<int>> graph;
vector<int> may3;
set<pair<int,int>> unidos;
void Init(int N_){
  graph.resize(N=N_);
  degree.resize(N);
}
void Link(int A,int B){
  if(canticriti==0){
    return;
  }
  if(asegu!=-1){
    if(A==asegu){
      degree[A]++;
    }else if(B==asegu){
      degree[B]++;
    }else{
      degree[A]++;
      degree[B]++;
      if(degree[A]>2 || degree[B]>2){
        canticriti=0;
      }
    }
  }else{
    unidos.insert({min(A,B),max(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){
        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