Submission #1240147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240147		guanex	Parachute rings (IOI12_rings)	C++20	38 / 100	4098 ms	103952 KiB

rings

#include<bits/stdc++.h>

using namespace std;

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

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{
  int ff[1000005];
  bool vis[1000005];
  int deg[1000005];
  bool ans = 1;
  int excl = 0;
  graph(int ex){
    excl = ex;
    for(int i = 0; i < 1000005; ++i){
      ff[i] = i;
      vis[i] = 0;
      deg[i] = 0;
    }
    for(int i = 0; i < 1000005; ++i){
      vis[i] = 1;
      if(i == ex)continue;
      for(auto e:ed[i]){
        if(e == ex)continue;
        deg[i]++;
        if(deg[i] >= 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;
    }
    ff[v] = u;
    return 1;
  }
  void updt(int u, int v){
    if(!ans){
      return;
    }
    if(u == excl){
      return;
    }
    if(v == excl) return;
    deg[u]++;
    deg[v]++;
    if(deg[u] == 3){
      ans = 0;
    }
    if(deg[v] == 3){
      ans = 0;
    }
    if(!jjoin(u, v)){
      ans = 0;
    }
  }
  bool 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(int i = 0; i < (int)good.size(); ++i){
      good[i].updt(A, B);
    }
    return;
  }
  //cout << "hola" << endl;
  if((int)ed[B].size() == 3){
    //cout << "camilo tiene retraso" << endl;
    triple = 1;
    possibles.push_back(B);
    for(auto &e:ed[B]){
      possibles.push_back(e);
    }
    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;
    possibles.push_back(A);
    for(auto &e:ed[A]){
      possibles.push_back(e);
    }
    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(int i = 0; i < (int)good.size(); ++i){
      ans += good[i].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: 0 / 14
• Subtask 5: 0 / 31