제출 #130648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
130648		dragonslayerit	낙하산 고리들 (IOI12_rings)	C++14	0 / 100	2504 ms	262148 KiB

rings

#include <vector>
#include <algorithm>
#include <cassert>

#include <cstdio>

std::vector<std::pair<int,int> > elist;

int N;

struct Graph{
  int ign;
  std::vector<int> deg;
  std::vector<int> uf;
  bool fail;
  std::vector<std::vector<int> > adj;
  Graph(int ign):ign(ign),deg(N),uf(N),fail(false),adj(N){
    for(int i=0;i<N;i++){
      uf[i]=i;
    }
  }
  int find(int a){
    while(a!=uf[a]){
      a=uf[a]=uf[uf[a]];
    }
    return a;
  }
  void merge(int a,int b){
    adj[a].push_back(b);
    adj[b].push_back(a);
    uf[find(a)]=find(b);
  }
  void add(int a,int b){
    if(a==ign||b==ign) return;
    //printf("G/{%d} += %d,%d\n",ign,a,b);
    if(++deg[a]>2) fail=true;
    if(++deg[b]>2) fail=true;
    if(find(a)==find(b)) fail=true;
    if(fail) return;
    merge(a,b);
  }
  std::vector<int> stk;
  std::vector<int> vis;
  bool dfs(int node,int parent){
    stk.push_back(node);
    vis[node]=1;
    for(int child:adj[node]){
      if(child==parent) continue;
      if(vis[child]){
	stk.erase(stk.begin(),std::find(stk.begin(),stk.end(),child));
	return true;
      }
      if(dfs(child,node)) return true;
    }
    stk.pop_back();
    return false;
  }
  std::vector<int> find_cycle(){
    //assert(stk.empty());
    vis.clear();
    vis.resize(N);
    for(int i=0;i<N;i++){
      if(!vis[i]&&dfs(i,i)){
	return stk;
      }
    }
    return {};
    //assert(0);
  }
}all(-1);

std::vector<int> cycle;

int branch;
std::vector<struct Graph> checkers;

void Init(int N_) {
  N = N_;
  all=Graph(-1);
}

void AddCandidate(int A){
  for(auto& c:checkers){
    if(c.ign==A) return;
  }
  checkers.emplace_back(A);
  for(auto e:elist){
    checkers.back().add(e.first,e.second);
  }
}

void AddBranch(int A){
  //printf("Branch %d\n",A);
  branch++;
  AddCandidate(A);
  for(int x:all.adj[A]){
    AddCandidate(x);
  }
}

void Link(int A, int B) {
  if(branch>2) return;
  bool loop=all.find(A)==all.find(B);
  all.deg[A]++,all.deg[B]++;
  all.merge(A,B);
  for(auto& c:checkers){
    c.add(A,B);
  }
  elist.push_back({A,B});
  
  if(all.deg[A]==3) AddBranch(A);
  if(all.deg[B]==3) AddBranch(B);
  if(loop){
    if(cycle.empty()){
      cycle=all.find_cycle();
    }else{
      all.fail=true;
    }
  }else{
    all.merge(A,B);
  }
}

int CountCritical() {
  if(branch==0){
    //printf("# deg 3+ =0\n");
    if(all.fail) return 0;
    if(cycle.empty()) return N;
    return cycle.size();
  }
  if(branch>2){
    //printf("# deg 3+ >2\n");
    return 0;
  }
  //printf("# deg 3+ in [1,2]\n");
  int ans=0;
  for(const auto& c:checkers){
    if(!c.fail){
      //printf("%d is ok\n",c.ign);
      ans++;
    }
  }
  return ans;
}

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