Submission #1020263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020263		anton	Parachute rings (IOI12_rings)	C++17	55 / 100	4086 ms	150024 KiB

rings

#include<bits/stdc++.h>

using namespace std;

struct DSU{
  int nbGroups =0;
  bool needs_op_buffer = false;
  vector<int> anc;
  vector<int> sz;
  vector<pair<int, pair<int, int>>> op_buffer;
  int nbCycles = 0;
  int szCycle= 0;

  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){
    
    if(needs_op_buffer)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--;

    if(needs_op_buffer)op_buffer.push_back({a, {anc[a], sz[a]}});
    if(needs_op_buffer)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_op(){
    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++;
      }
  }
  void undo_buffer(){
    while(op_buffer.size()>0){
      undo_op();
    }
  }
};

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

DSU boringDSU, fullDSU;
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;
}

int state = 0;
//0 = only deg<=2
//1 only deg <=3, some interesting left
//2 One deg =4, some interesting
//3 no interesting left
void changeDeg(int u, int d){
  
  if(deg[u]>=3){
    above3--;
  }
  if(deg[u] >= 4){
    above4--;
  }
  oc[deg[u]]--;
  deg[u] +=d;
  assert(deg[u]>=0);
  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.push_back(i);
    idInteresting[i] = i;
  }
  oc[0]  =N;
  boringDSU = DSU(N);
  fullDSU = DSU(N);
  boringDSU.needs_op_buffer = true;
}

void updInteresting(int u, bool tolerant){
  unordered_set<int> close;
  if(tolerant){
    for(auto e: adj[u]){
        close.insert(e);
    }
  }
  close.insert(u);
  vector<int> new_interesting;
  for(int i = 0; i<interesting.size(); i++){
    auto it = interesting[i];
    if(close.find(it)  == close.end()){
      isInteresting[it] = false;
      //cerr<<"removing "<<*it<<endl;
      for(auto ee: adj[it]){
        if(!isInteresting[ee]){
          boringDSU.merge(it, ee);
        }
      }
    }
    else{
      idInteresting[it] =new_interesting.size();
      new_interesting.push_back(it);
    }
  }

  swap(interesting, new_interesting);
}

void recalcDeg(){
    for(int i = 0; i<N; i++){
        if(deg[i] < 4){
          changeDeg(i, -deg[i]);
          for(auto v: adj[i]){
              if(deg[v] != 4){
                   changeDeg(i, 1);
              }
          }
        }
    }
}

int calcLinks(int l, int r){
  int res=  0;
  if(l == r){
    int iRem = interesting[l];
    for(auto e: adj[iRem]){
      changeDeg(e, -1);
      changeDeg(iRem, -1);
    }
    if((oc[0]-1)*2 + oc[1] == (boringDSU.nbGroups-1)*2 && above3 ==0) res= 1;

    for(auto e: adj[iRem]){
      changeDeg(e, 1);
      changeDeg(iRem, 1);
    }
    return res;
  }
  int mid = (l+r)/2;
  int begin_size = boringDSU.op_buffer.size();

  for(int i = l; i<=mid; i++){
    int iAdd =interesting[i];
    for(auto e: adj[iAdd]){
      if((!isInteresting[e]) || !(mid+1<=idInteresting[e] && idInteresting[e]<=r)){
        boringDSU.merge(e, iAdd);
      }
    }
  }
  res += calcLinks(mid+1, r);
  while(boringDSU.op_buffer.size()>begin_size){
    boringDSU.undo_op();
  }

  for(int i = mid+1; i<=r; i++){
    int iAdd =interesting[i];

    for(auto e: adj[iAdd]){
      if((!isInteresting[e]) || !(l<=idInteresting[e] && idInteresting[e]<=mid)){
        boringDSU.merge(e, iAdd);
      }
    }
  }

  res += calcLinks(l, mid);
  while(boringDSU.op_buffer.size()>begin_size){
    boringDSU.undo_op();
  }
  return res;
}

void Link(int A, int B) {
    if(interesting.size()== 0){
        return;
    }

    fullDSU.merge(A, B);

    adj[A].push_back(B);
    adj[B].push_back(A);

    if(deg[A] <4 && deg[B] < 4){
        changeDeg(A, +1);
        changeDeg(B, +1);
    }
    if((deg[A]== 3 || deg[B]==3)){

        if(deg[A] != 3){
        swap(A, B);
        }
        updInteresting(A, true);
        if(deg[B] == 3){
            updInteresting(B, true);
        }
    }

    if(isInteresting[A] || isInteresting[B]){

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

    if((deg[A] == 4 || deg[B]== 4) && above4 == 1){
        if(deg[A] != 4){
            swap(A, B);
        }
        updInteresting(A, false);
        if(deg[B] == 4){
            updInteresting(B, false);
        } 
        recalcDeg();
    }
}

int prev_res=  0;

int calc(){
  if(interesting.size() == 0){
    return 0;
  }
  else{
    if(above4 == 1){
        if((oc[0])*2 + oc[1] == (boringDSU.nbGroups-1)*2 && above3 ==1){
            return 1;
        }
        return 0;
    }
    else if(above3>=1){
      return calcLinks(0, interesting.size()-1);
    }
    else{
      if(fullDSU.nbCycles == 0){
        return N;
      }
      else if(fullDSU.nbCycles == 1){
        return fullDSU.szCycle;
      }
      else{
        return 0;
      }
    }
  }
}

int CountCritical() {
  //cerr<<oc[0]<<" "<<oc[1]<<" "<<oc[2]<<" "<<oc[3]<<endl;
  prev_res = calc();
  return prev_res;

}

Compilation message (stderr)

rings.cpp: In function 'void updInteresting(int, bool)':
rings.cpp:154:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   for(int i = 0; i<interesting.size(); i++){
      |                  ~^~~~~~~~~~~~~~~~~~~
rings.cpp: In function 'int calcLinks(int, int)':
rings.cpp:215:35: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  215 |   while(boringDSU.op_buffer.size()>begin_size){
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
rings.cpp:230:35: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  230 |   while(boringDSU.op_buffer.size()>begin_size){
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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