Submission #1152213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152213		julia_08	Parachute rings (IOI12_rings)	C++20	100 / 100	528 ms	77188 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], ciclo[5];

int ciclo_geral[MAXN], init[MAXN];

int adj[MAXN][3];

int sz_ciclo = 0;

bool ok = true;

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;

void dsu_init(int x){

  if(init[cand[x]]) return;

  init[cand[x]] = 1;

  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 ciclo[x] = 1;

  }

}

void Init(int n_){

  n = n_;

  ok = true;

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

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

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

    ciclo[j] = 0;
  }

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

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

    cand.push_back(i);
  }

  cnt_3 = cnt_4 = cnt_ciclo = 0;

}

void check_4(int v){

  assert((int) cand.size() <= 4); // passou pelo check_3 em algum momento

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

  cand.clear();

  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(int i=0; i<deg[v]; i++) if(good[adj[v][i]]) to_add.push_back(adj[v][i]);

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

  cand.clear();

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

  assert((int) cand.size() <= 4);
}

void Link(int a, int b){

  if(!ok) return;

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

  if(deg[a] <= 3) adj[a][deg[a] - 1] = b;
  if(deg[b] <= 3) adj[b][deg[b] - 1] = 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();

    ok = false;

    return;
  }

  if(deg[a] == 4) check_4(a);
  if(deg[b] == 4) check_4(b);

  if(!ok) return;

  if(deg[a] == 3) check_3(a);
  if(deg[b] == 3) check_3(b);

  // cand atualizado!

  edges.push_back({a, b});

  if(cnt_3 > 0){

    assert((int) cand.size() <= 4);

    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 ciclo[i] = 1;

    }
  }

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

  if(cnt_ciclo > 1) ok = false;

  /*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(!ok) return 0;

  if(cnt_ciclo > 1) return 0;

  if(cnt_3 == 0){
    if(cnt_ciclo == 0) return n;
    return sz_ciclo;
  }

  assert((int) cand.size() <= 4);

  int ans = 0;

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

  return ans;
}

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