Submission #1189132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189132		julia_08	Parachute rings (IOI12_rings)	C++20	100 / 100	837 ms	125524 KiB

rings

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

const int MAXN = 1e6 + 10;

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

int id[MAXN];

int deg[MAXN][5];

set<int> comp_ciclos;
vector<int> cand_critical;

vector<int> adj[MAXN];

vector<pair<int, int>> links;

bool first_update;

int deg_3, deg_4;

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];

}

int n;

void Init(int n_){

  n = n_;

  comp_ciclos.clear();
  cand_critical.clear();

  deg_3 = deg_4 = 0;

  first_update = true;

  for(int i=1; i<=n; i++) id[i] = -1;

  for(int i=1; i<=n; i++){
    for(int j=0; j<5; j++){
      sz[i][j] = 1;
      pai[i][j] = i;
      deg[i][j] = 0;
    }
  }

}

void dsu_init(int v){

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

    if(id[v] == -1) continue;

    if(a == v || b == v) continue;

    if(get(a, id[v]) == get(b, id[v])){
      id[v] = -1;

    } else{
      dsu_union(a, b, id[v]);
      if(deg[a][id[v]] > 1 || deg[b][id[v]] > 1) id[v] = -1;
    }

    if(id[v] == -1) continue;

    deg[a][id[v]] ++;
    deg[b][id[v]] ++;

  }

}

void Link(int a, int b){

  a ++;
  b ++;

  links.push_back({a, b});

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

  for(auto v : cand_critical){

    if(id[v] == -1) continue;

    if(a == v || b == v) continue;

    if(get(a, id[v]) == get(b, id[v])){
      id[v] = -1;

    } else{
      dsu_union(a, b, id[v]);
      if(deg[a][id[v]] > 1 || deg[b][id[v]] > 1) id[v] = -1;
    }

    if(id[v] == -1) continue;

    deg[a][id[v]] ++;
    deg[b][id[v]] ++;

  }

  if(get(a, 0) == get(b, 0)){
    comp_ciclos.insert(get(a, 0));

  } else dsu_union(a, b, 0);

  deg[a][0] ++;
  deg[b][0] ++;

  if(deg[a][0] == 3) deg_3 ++;
  if(deg[a][0] == 4) deg_4 ++;

  if(deg[b][0] == 3) deg_3 ++;
  if(deg[b][0] == 4) deg_4 ++;

  vector<int> new_cand_critical;

  bool update_cand_critical = false;

  if(deg_4 == 1 && (deg[a][0] >= 4 || deg[b][0] >= 4)){
    update_cand_critical = true;
    if(deg[a][0] >= 4) new_cand_critical = {a};
    if(deg[b][0] >= 4) new_cand_critical = {b};

  } else if(deg[a][0] == 3 && deg[b][0] == 3){

    update_cand_critical = true;

    vector<int> cand_a = {a, adj[a][0], adj[a][1], adj[a][2]};
    vector<int> cand_b = {b, adj[b][0], adj[b][1], adj[b][2]};

    for(auto v : cand_a){
      bool ok = false;
      for(auto u : cand_b) ok |= (u == v);
      if(ok) new_cand_critical.push_back(v);
    }

  } else if(deg[a][0] == 3 || deg[b][0] == 3){

    if(deg[a][0] != 3) swap(a, b);

    update_cand_critical = true;
    new_cand_critical = {a, adj[a][0], adj[a][1], adj[a][2]};

  }

  if(update_cand_critical){

    if(first_update){

      for(auto v : new_cand_critical){

        cand_critical.push_back(v);
        id[v] = cand_critical.size();

        dsu_init(v);

      }

      first_update = false;

    } else{

      for(auto v : cand_critical){

        bool ok = false;

        for(auto u : new_cand_critical) ok |= (u == v);

        if(!ok) id[v] = -1;

      }

    }

  }

}

int CountCritical(){

  if(deg_4 > 1) return 0;

  if(deg_3 == 0){

    if(comp_ciclos.size() > 1) return 0;

    if(comp_ciclos.size() == 1) return sz[get(*comp_ciclos.begin(), 0)][0];

    return n;

  }

  int ans = 0;

  for(auto v : cand_critical) if(id[v] != -1) ans ++;

  return ans;

}

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