Submission #1020152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020152		anton	Parachute rings (IOI12_rings)	C++17	0 / 100	729 ms	139716 KiB

rings

#include<bits/stdc++.h>

using namespace std;


int nbCycles = 0;
int szCycle= 0;

struct DSU{
  int nbGroups =0;
  vector<int> anc;
  vector<int> sz;
  vector<pair<int, pair<int, int>>> op_buffer;

  DSU(){};
  DSU(int l){
    anc.resize(l);
    sz.resize(l);
    for(int i = 0; i<l; i++){
      anc[i] = i;
      sz[i] = 1;
    }
    nbGroups = l;
  }
  int c(int u){
    op_buffer.push_back({u, {anc[u], sz[u]}});
    if(anc[u] == u){
      return u;
    }
    int v= c(anc[u]);
    anc[u] =v;
    return v;
  }

  void merge(int a, int b){
    //cerr<<"merging "<<a<<" "<<b<<endl;
    a = c(a);
    b= c(b);
    if(a==b){
      nbCycles ++;
      szCycle = sz[a];
      return;
    }
    nbGroups--;

    op_buffer.push_back({a, {anc[a], sz[a]}});
    op_buffer.push_back({b, {anc[b], sz[b]}});

    if(sz[a]>sz[b]){
      swap(a, b);
    }

    anc[a] = b;
    sz[b] += sz[a];  
  }

  void undo_buffer(){
    while(op_buffer.size()>0){
      auto e= op_buffer.back();
      if(anc[e.first] == e.first){
        nbGroups--;
      }
      op_buffer.pop_back();
      anc[e.first] = e.second.first;
      sz[e.first] = e.second.second;
      if(anc[e.first] == e.first){
        nbGroups++;
      }
    }
  }
};

int N;
const int MAX_N= 1e6;
vector<int> adj[MAX_N];
unordered_set<int> interesting;
bool isInteresting[MAX_N];
int deg[MAX_N], oc[MAX_N];

DSU curDSU;
int above3= 0;
int above4 = 0;



DSU recalcDSU(){
  DSU newDSU(N);
  for(int iV = 0; iV<N; iV++){
    
      for(auto u: adj[iV]){
        if(!(isInteresting[u] || isInteresting[iV])){
          newDSU.merge(iV, u);
        }
      }
    
  }

  newDSU.op_buffer.clear();
  return newDSU;
}

bool lost3 = false;

int count3(int u){
  int res= 0;
  for(auto e: adj[u]){
    if(deg[e]>=3){
      res++;
    }
  }
  return res;
}
void changeDeg(int u, int d){
  
  if(deg[u]>=3){
    above3--;
  }
  if(deg[u] >= 4){
    above4--;
  }
  oc[deg[u]]--;
  deg[u] +=d;
  oc[deg[u]] ++;
  if(deg[u]>=3){
    above3++;
  }
  if(deg[u] >= 4){
    above4++;
  }
}


void Init(int N_) {

  
  N = N_;
  fill(&oc[0], &oc[N], 0);
  fill(&isInteresting[0], &isInteresting[N], true);

  for(int i = 0; i<N; i++){
    interesting.insert(i);
  }
  oc[0]  =N;

  curDSU = DSU(N);

}

bool check_possible(){

  return interesting.size()>0;
}



void updInteresting(int u){
  unordered_set<int> close;
  for(auto e: adj[u]){
    close.insert(e);
  }
  close.insert(u);
  for(auto it = interesting.begin(); it!=interesting.end(); ){
    if(close.find(*it)  == close.end()){
      isInteresting[*it] = false;
      for(auto ee: adj[*it]){
        if(!isInteresting[ee]){
          curDSU.merge(*it, ee);
        }
      }
      it = interesting.erase(it);
      
    }
    else{
      ++it;
    }
  }
}
bool changed = true;

void clear_interesting(){
  unordered_set<int> new_interesting;
  for(auto e: interesting){
    if(deg[e] != 4){
      isInteresting[e] = false;
    }
    else{
      new_interesting.insert(e);
    }
  }

  for(auto e: interesting){
    for(auto ee: adj[e]){

      if(!(isInteresting[ee] ||isInteresting[e])){
        curDSU.merge(e, ee);
      }
    }
  }

  swap(interesting, new_interesting);
}

void Link(int A, int B) {
  changed = true;
  if(above4>1 || lost3){
    return;
  }

  adj[A].push_back(B);
  changeDeg(A, +1);
  adj[B].push_back(A);
  changeDeg(B, +1);
  if(above4 == 0 && (deg[A]== 3 || deg[B]==3)){

    if(deg[A] != 3){
      swap(A, B);
    }
    updInteresting(A);
    if(deg[B] == 3){
      updInteresting(B);
    }
    curDSU = recalcDSU();
  }
  else if(isInteresting[A] || isInteresting[B]){

  }
  else{
    curDSU.merge(A, B);
    curDSU.op_buffer.clear();
  }

  if((deg[A] == 4 || deg[B]== 4) && above4 == 1){
    clear_interesting();
  }

  if(deg[A]>=4){
    if(count3(A)<above3-1){
      lost3 = true;
    }
  }
  if(deg[B]>=4){
    if(count3(B)<above3-1){
      lost3 = true;
    }
  }

  if(above4 == 0){
    if(!check_possible()){
      lost3 = true;
    }
  }

}

int prev_res=  0;

int calc(){
  if(above4>1 || lost3){
    return 0;
  }
  else{
    if(above3>=1){
      int res= 0;

      for(auto iAdd: interesting){
        for(auto e: adj[iAdd]){
          if(!isInteresting[e]){
            changeDeg(e, -1);
          }
          changeDeg(iAdd, -1);
        }
      }


      for(auto iRem: interesting){
        if(deg[iRem]>=4 || above4 ==0){
          for(auto iAdd: interesting){
            if(iAdd!=iRem){
              for(auto e: adj[iAdd]){
                if(e!=iRem){
                  curDSU.merge(e, iAdd);
                  if(!isInteresting[e]){
                    changeDeg(e, 1);
                  }
                  changeDeg(iAdd, 1);
                }
              }
            }
          }

          
          if((oc[0]-1)*2 + oc[1] == (curDSU.nbGroups-1)*2 && above3 ==0){
            res++;
          }


          for(auto iAdd: interesting){
            if(iAdd!=iRem){
              for(auto e: adj[iAdd]){
                if(e!=iRem){
                  if(!isInteresting[e]){
                    changeDeg(e, -1);
                  }
                  changeDeg(iAdd, -1);
                }
              }
            }
          }
          curDSU.undo_buffer();
        }
      }


      for(auto iAdd: interesting){
        for(auto e: adj[iAdd]){
          if(!isInteresting[e]){
            changeDeg(e, 1);
          }
          changeDeg(iAdd, 1);
        }
      }
      return res;
    }
    else{
      if(nbCycles == 0){
        return N;
      }
      else if(nbCycles == 1){
        return szCycle;
      }
      else{
        return 0;
      }
    }
  }
}

int CountCritical() {
  if(!changed){
    return prev_res;
  }
  prev_res = calc();
  return prev_res;

}

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