Submission #1152186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152186		julia_08	Parachute rings (IOI12_rings)	C++20	0 / 100	4094 ms	44356 KiB

rings

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 10;

int pai[MAXN][5], sz[MAXN][5];

int deg[MAXN];

int good[MAXN];

int ciclo[5];

vector<int> adj[MAXN];

int n;

int get(int v, int x){
  if(v == pai[v][x]) return v;
  return pai[v][x] = get(pai[v][x], x);
}

void dsu_union(int a, int b, int x){

  a = get(a, x);
  b = get(b, x);

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

  pai[a][x] = b;
  sz[b][x] += sz[a][x];
}

vector<pair<int, int>> edges;

vector<int> cand;

int cnt_4 = 0, cnt_3 = 0;

int cnt_ciclo = 0;

pair<int, int> id_ciclo = {-1, -1};

void dsu_init(int x){

  for(int i=0; i<n; i++) pai[i][x] = i, sz[i][x] = 1;

  ciclo[x] = 0;

  for(auto [a, b] : edges){

    if(a == cand[x] || b == cand[x]) continue;

    if(get(a, x) != get(b, x)) dsu_union(a, b, x);
    else{
      if(ciclo[x] == 0) cnt_ciclo ++;
      ciclo[x] = 1;
      id_ciclo = {a, x};
    }

  }

}

void Init(int n_){

  n = n_;

  cand.clear();
  edges.clear();

  for(int i=0; i<n; i++){

    adj[i].clear();

    for(int j=0; j<5; j++) dsu_init(j);

    deg[i] = 0;
    good[i] = 1;

  }

  cnt_3 = cnt_4 = cnt_ciclo = 0;

}

void check_4(int v){

  for(auto x : cand) if(x != v) good[x] = 0;

  cand.clear();

  cnt_ciclo = 0;

  if(good[v]){
    cand.push_back(v);
    dsu_init(0);
  }
}

void check_3(int v){

  vector<int> to_add;

  if(good[v]) to_add.push_back(v);

  for(auto j : adj[v]) if(good[j]) to_add.push_back(j);

  for(auto x : cand) good[x] = 0;

  cand.clear();

  cnt_ciclo = 0;

  for(auto x : to_add){
    cand.push_back(x);
    good[x] = 1;
    dsu_init(cand.size() - 1);
  }
}

void Link(int a, int b){

  deg[a] ++, deg[b] ++;

  adj[a].push_back(b);
  adj[b].push_back(a);

  if(deg[a] == 4) cnt_4 ++;
  if(deg[b] == 4) cnt_4 ++;

  if(deg[a] == 3) cnt_3 ++;
  if(deg[b] == 3) cnt_3 ++;

  if(cnt_4 > 1){
    for(auto x : cand) good[x] = 0;
    cand.clear();

    cnt_ciclo = 0;

  } else if(deg[a] == 4){
    check_4(a);

  } else if(deg[b] == 4){
    check_4(b);

  } else if(deg[a] == 3){
    check_3(a);

  } else if(deg[b] == 3) check_3(b);

  // cand atualizado!

  edges.push_back({a, b});

  for(int i=0; i<(int) cand.size(); i++){

    if(a == cand[i] || b == cand[i]) continue;

    if(get(a, i) != get(b, i)) dsu_union(a, b, i);
    else{
      if(ciclo[i] == 0) cnt_ciclo ++;
      ciclo[i] = 1;
      id_ciclo = {a, i};
    }

  }

  if(get(a, 4) != get(b, 4)) dsu_union(a, b, 4);
  else{
    if(ciclo[4] == 0) cnt_ciclo ++;
    ciclo[4] = 1;
    id_ciclo = {a, 4};
  }

  /*cout << "after link " << a << " " << b << ", cnt_ciclo =  " << cnt_ciclo << "\n";

  for(int i=0; i<(int) cand.size(); i++){
    cout << cand[i] << " " << ciclo[i] << "\n";
  }

  cout << ".\n";
  */

}

int CountCritical(){

  // cout << "cnt_ciclo = " << cnt_ciclo << "\n";

  if(cnt_ciclo > 1) return 0;

  if(cnt_3 == 0){
    if(cnt_ciclo == 0) return n;
    return sz[get(id_ciclo.first, id_ciclo.second)][id_ciclo.second];
  }

  int ans = 0;

  for(int i=0; i<(int) cand.size(); i++) if(!ciclo[i]) ans ++;

  return ans;
}

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