Submission #1020800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020800		anton	Parachute rings (IOI12_rings)	C++17	100 / 100	1240 ms	148044 KiB

rings

#include<bits/stdc++.h>

using namespace std;


struct DSU{
  vector<int> sz, anc, oc, deg;
  int nbG= 0, nbC= 0, csz = 0, above3 = 0;
  DSU(){};
  DSU(int l){
    sz.resize(l);
    anc.resize(l);
    oc.resize(l);
    deg.resize(l);
    nbG = l;
    for(int i = 0; i<l; i++){
      anc[i] = i;
      sz[i] = 1;
      deg[i] = 0;
    }
    oc[0]= l;
  }


  int c(int u){
    if(anc[u] == u){
      return u;
    }
    int v= c(anc[u]);
    anc[u] = v;
    return v;
  }

  void changeDeg(int u, int d){
    oc[deg[u]]--;
    if(deg[u]>=3){
      above3--;
    }
    deg[u]+=d;
    if(deg[u]>=3){
      above3++;
    }
    oc[deg[u]]++;
  }

  void merge(int a, int b){

    changeDeg(a, +1);
    changeDeg(b, +1);
    a=  c(a);
    b = c(b);
    if(a==b){
      nbC++;
      csz = sz[a];
      return;
    }
    nbG--;

    if(sz[a]<sz[b]){
      swap(a, b);
    }
    
    anc[b]= a;
    sz[a]+=sz[b];
  }
};

struct multiDSU{
  unordered_map<int, DSU> dsus;

  multiDSU(){};
  multiDSU(int l, unordered_set<int>& intresting){
    for(auto e: intresting){
      dsus[e] = DSU(l);
    }
    dsus[-1] = DSU(l);
  }

  void merge(int a, int b){
    for(auto it = dsus.begin(); it!=dsus.end(); ++it){
      if(it->first != a && it->first != b){
        //cerr<<"merging "<<a<<" "<<b<<" "<<it->first<<endl;
        it->second.merge(a, b);
      }
    }
  }
};
const int MAX_N = 1e6;
vector<int> adj[MAX_N];
DSU beginDSU;
multiDSU endDSU;

int N;
int state = 0;
//0 = only 2s
//1 = have a 3 or more
void Init(int _N){
  N = _N;
  beginDSU = DSU(N);
}
void Link(int a, int b){
  if(state == 0){
    beginDSU.merge(a, b);
    adj[a].push_back(b);
    adj[b].push_back(a);
    if(adj[a].size()<3){
      swap(a, b);
    }
    if(adj[a].size() >= 3){
      state = 1;
      unordered_set<int> intresting;
      for(auto o: adj[a]){
        intresting.insert(o);
      }
      intresting.insert(a);
      endDSU = multiDSU(N, intresting);
      for(int i = 0; i<N; i++){
        for(auto e: adj[i]){
          if(i<e){
            endDSU.merge(e, i);
          }
        }
      }
    }
  }
  else{
    endDSU.merge(a, b);
  }
}

int CountCritical(){
  if(state== 0){
    if(beginDSU.nbC == 0){
      return N;
    }
    else if(beginDSU.nbC == 1){
      return beginDSU.csz;
    }
    else{
      return 0;
    }
  }
  else{
    int res= 0;
    for(auto it = endDSU.dsus.begin(); it!=endDSU.dsus.end(); ){
      if(it->first != -1){
        if((it->second.oc[0]-1)*2 + it->second.oc[1] == 2*(it->second.nbG-1) && it->second.above3 == 0){
          res++;
          ++it;
        }
        else{
          it = endDSU.dsus.erase(it);
        }
      }
      else{
        ++it;
      }
    }
    return res;
  }
}

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