Submission #130622

#	Time	Username	Problem	Language	Result	Execution time	Memory
130622		dragonslayerit	Parachute rings (IOI12_rings)	C++14	0 / 100	4045 ms	262144 KiB

rings

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

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;
    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(){
    vis.clear();
    vis.resize(N);
    for(int i=0;i<N;i++){
      if(!vis[i]&&dfs(i,i)){
	return stk;
      }
    }
    assert(0);
  }
  */
}all(-1);

std::vector<int> cycle;
std::vector<int> branch;

std::vector<struct Graph> checkers;

void Init(int N_) {
  N = N_;
  //all=Graph(-1);
  for(int i=0;i<N;i++){
    checkers.emplace_back(i);
  }
}

void AddBranch(int A){
  branch.push_back(A);
  checkers.emplace_back(A);
  for(auto e:elist){
    checkers.back().add(e.first,e.second);
  }
}

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

int CountCritical() {
  /*
  if(branch.empty()){
    if(all.fail) return 0;
    if(cycle.empty()) return N;
    return cycle.size();
  }
  if(branch.size()>2) return 0;
  */
  int ans=0;
  for(const auto& c:checkers){
    if(!c.fail) ans++;
  }
  return ans;
}

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