Submission #1037450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037450		spacewalker	Parachute rings (IOI12_rings)	C++17	100 / 100	299 ms	90124 KiB

rings

#include <bits/stdc++.h>

using namespace std;

struct ComponentUnionFind {
  bool is_chains = true;
  vector<int> par;
  vector<int> _degree;
  int extra_edges = 0;
  ComponentUnionFind(int n) : par(n, -1), _degree(n, 0) {}
  int find(int i) {
    return par[i] < 0 ? i : (par[i] = find(par[i])); 
  }
  int csize(int i) {
    return -par[find(i)];
  }
  int degree(int i) {
    return _degree[i];
  }
  bool join(int i, int j) {
    ++_degree[i]; ++_degree[j];
    if (_degree[i] > 2 || _degree[j] > 2) is_chains = false;
    int ir = find(i), jr = find(j);
    if (ir == jr) {
      ++extra_edges;
      is_chains = false;
      return false;
    }
    if (par[ir] > par[jr]) {
      swap(i, j); swap(ir, jr);
    }
    par[ir] += par[jr]; par[jr] = ir;
    return true;
  }
};

ComponentUnionFind create_from_ban(const vector<pair<int, int>> &edge_list, int n, int banned) {
  ComponentUnionFind cuf(n);
  for (auto [u, v] : edge_list) {
    if (u != banned && v != banned) cuf.join(u, v);
  }
  return cuf;
}

struct ParachuteRings {
  int n;
  vector<pair<ComponentUnionFind, int>> cufs;
  vector<pair<int, int>> edge_list;
  // size of the first cycle formed
  optional<int> critical_cycle_size;
  bool spoiled;
  ParachuteRings(int n) : n(n), cufs{{ComponentUnionFind(n), -1}}, spoiled(false) {}
  ParachuteRings() {} 
  int count_critical() {
    if (spoiled) return 0;
    // here, we know the graph is NOT spoiled
    else if (cufs.size() > 1) {
      int ans = 0;
      for (auto &[cuf, _] : cufs) if (cuf.is_chains) ++ans;
      return ans;
    } else {
      // if we have no critical cycle, everything must still be chains
      return critical_cycle_size.value_or(n);
    }
  }
  
  void reset_cufs(int i) {
    vector<pair<ComponentUnionFind, int>> new_cufs;
    vector<int> bans;
    for (auto [u, v] : edge_list) {
      if (u == i) bans.push_back(v);
      if (v == i) bans.push_back(u);
    }
    bans.push_back(i);
    for (int v : bans) new_cufs.emplace_back(create_from_ban(edge_list, n, v), v);
    cufs = new_cufs;
  }

  void link(int i, int j) {
    edge_list.emplace_back(i, j);
    if (spoiled) return;
    if (cufs.size() > 1) {
      for (auto &[cuf, banned] : cufs) {
        if (!(i == banned || j == banned)) cuf.join(i, j);
      }
    } else {
      auto &cuf = cufs[0].first;
      bool cycle_created = !cuf.join(i, j);
      if (cuf.degree(i) > 2 || cuf.degree(j) > 2) {
        if (cuf.degree(i) > 2) reset_cufs(i);
        else reset_cufs(j);
      } else {
        // all nodes still have degree <= 2
        // now, we must check for cycles
        // here, i guarantee cuf is still valid
        if (cycle_created) {
          if (cuf.extra_edges >= 2) {
            // we have two disjoint cycles, spoil the graph now
            spoiled = true;
          } else {
            critical_cycle_size = cuf.csize(i);
          }
        }
      }
      // if i fuck up here because i access cuf when i invalidated it that is
      // unironically a "muh memory safety!!!!!" moment
    }
  }
  void dump_state() {
    return;
    cerr << "!!! STATE DUMP " << endl;
    if (spoiled) cerr << "spoiled" << endl;
    else {
      cerr << "crit cycle " << critical_cycle_size.value_or(-1) << endl;
      cerr << cufs.size() << "simulations" << endl;
      for (auto &[cuf, banned] : cufs) {
        cerr << "cuf with ban" << banned << " = " << cuf.is_chains << endl;
      }
    }
  }
};

ParachuteRings pr;

void Init(int N) {
  pr = ParachuteRings(N);
  pr.dump_state();
}

void Link(int A, int B) {
  pr.link(A, B);
  pr.dump_state();
}

int CountCritical() {
  return pr.count_critical();
  pr.dump_state();
}

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