Submission #1240124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240124		guanex	Parachute rings (IOI12_rings)	C++20	52 / 100	87 ms	33604 KiB

rings

#include<bits/stdc++.h>

using namespace std;

int N;
vector<vector<int>> ed(100005, (vector<int>){});
vector<int> cycles;
vector<int> possibles;
bool triple = 0;
int f[100005];
int len[100005];

void Init(int N_) {
  N = N_;
  triple = false;
  cycles.clear();
  possibles.clear();
  for(int i = 0; i <= N_; ++i){
    ed[i].clear();
    f[i] = i;
    len[i] = 1;
  }
}

struct graph{
  vector <int> ff;
  vector <int> llen;
  vector <int> vis;
  vector<vector<int>> edd;
  int ans = 1;
  int excl = 0;
  graph(int ex){
    ff = vector<int> (100005,0);
    llen = vector <int> (100005,0);
    vis = vector <int> (100005,0);
    excl = ex;
    edd.assign(100005, vector<int>({}));
    for(int i = 0; i < 100005; ++i){
      edd[i].clear();
      ff[i] = i;
      llen[i] = 1;
    }
    for(int i = 0; i < 100005; ++i){
      vis[i] = 1;
      if(i == ex)continue;
      for(auto e:ed[i]){
        if(e == ex)continue;
        edd[i].push_back(e);
        if((int)edd[i].size() >= 3){
          ans = 0;
        }
        if(vis[e] == 0)continue;
        if(!jjoin(i, e)){
          ans = 0;
        }
      }
    }
  };
  int father(int no){
    //cout << "check " << no << " " << f[no] << endl;
    if(ff[no] == no){
      return no;
    }
    return ff[no] = father(ff[no]);
  } 
  bool jjoin(int u, int v){
    u = father(u);
    v = father(v);
    if(u == v){
      return 0;
    }
    if(llen[v] > llen[u]){
      swap(u, v);
    }
    llen[u] += llen[v];
    ff[v] = u;
    return 1;
  }
  void updt(int u, int v){
    if(u == excl){
      return;
    }
    if(v == excl) return;
    edd[u].push_back(v);
    edd[v].push_back(u);
    if((int)edd[u].size() == 3){
      ans = 0;
    }
    if((int)edd[v].size() == 3){
      ans = 0;
    }
    if(!jjoin(u, v)){
      ans = 0;
    }
  }
  int ask(){
    return ans;
  }
};

vector<graph> good;

int ffather(int no){
  //cout << "check " << no << " " << f[no] << endl;
  if(f[no] == no){
    return no;
  }
  return f[no] = ffather(f[no]);
}

bool join(int u, int v){
  u = ffather(u);
  v = ffather(v);
  if(u == v){
    return 0;
  }
  if(len[v] > len[u]){
    swap(u, v);
  }
  len[u] += len[v];
  f[v] = u;
  return 1;
}

void Link(int A, int B) {
  //cout << "linking" << good.size() << " " << triple << endl;
  ed[A].push_back(B);
  ed[B].push_back(A);
  //return;
  if(triple){
    //cout << good.size() << endl;
    for(auto &e:good){
      e.updt(A, B);
    }
    return;
  }
  //cout << "hola" << endl;
  if((int)ed[B].size() == 3){
    //cout << "camilo tiene retraso" << endl;
    triple = 1;
    graph g(B);
    good.push_back(g);
    graph gg(ed[B][0]);
    graph ggg(ed[B][1]);
    graph gggg(ed[B][2]);
    good.push_back(gg);
    good.push_back(ggg);
    good.push_back(gggg);
    return;
  }

  if((int)ed[A].size() == 3){
    triple = 1;
    graph g(A);
    good.push_back(g);
    graph gg(ed[A][0]);
    graph ggg(ed[A][1]);
    graph gggg(ed[A][2]);
    good.push_back(gg);
    good.push_back(ggg);
    good.push_back(gggg);
    return;
  }
  if(!join(A, B)){
    cycles.push_back(len[ffather(A)]);
    return;
  }
    
}

int CountCritical() {
  //cout << "ayuda"<<endl;
  if(triple){
    int ans = 0;
    for(auto &e:good){
      ans += e.ask();
    }
    return ans;
  }else{
    if((int)cycles.size() == 0){
      return N;
    }else if((int)cycles.size() == 1){
      return cycles[0];
    }else{
      return 0;
    }
  }
}

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