Submission #596063

#	Time	Username	Problem	Language	Result	Execution time	Memory
596063		Mamedov	Parachute rings (IOI12_rings)	C++17	100 / 100	593 ms	53040 KiB

rings

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct DSU {
  int components;
  vector<int>par;
  DSU(){}
  DSU(int n) {
    par.assign(n, -1);
    components = n;
  }
  void init(int n) {
    par.assign(n, -1);
    components = n;
  }
  int Find(int u) {
    if (par[u] < 0) return u;
    else return par[u] = Find(par[u]);
  }
  bool Union(int u, int v) {
    u = Find(u);
    v = Find(v);
    if (u != v) {
      if (par[u] > par[v]) {
        swap(u, v);
      }
      par[u] += par[v];
      par[v] = u;
      --components;
      return true;
    } else {
      return false;
    }
  }
};

int N, critical, cycle;
DSU dsu[4];
bool isCritical[4];
int root[4];
vpii edges;
vi deg[4];

void Init(int N_) {
  N = N_;
  critical = N;
  cycle = 0;
  for (int i = 0; i < 4; ++i) {
    dsu[i].init(N);
    deg[i].assign(N, 0);
    root[i] = -1;
  }
}

void Link(int A, int B) {
  if (!critical) return;
  if (root[0] == -1) {
    edges.eb(mpr(A, B));
    deg[0][A]++;
    deg[0][B]++;
    if (deg[0][A] == 3) {
      root[0] = A;
    } else if (deg[0][B] == 3) {
      root[0] = B;
    }
    if (root[0] != -1) {
      int id = 0;
      for (pii e : edges) {
        if (e.f == root[0] || e.s == root[0]) {
          root[++id] = e.f + e.s - root[0];
        }
      }
      dsu[0].init(N);
      deg[0].assign(N, 0);
      critical = 4;
      for (int i = 0; i < 4; ++i) {
        isCritical[i] = true;
        for (pii e : edges) {
          if (e.f != root[i] && e.s != root[i]) {
            deg[i][e.f]++;
            deg[i][e.s]++;
            if (!dsu[i].Union(e.f, e.s) || deg[i][e.f] >= 3 || deg[i][e.s] >= 3) {
              isCritical[i] = false;
              --critical;
              break;
            }
          }
        }
      }
    } else {
      if (!dsu[0].Union(A, B)) {
        ++cycle;
        if (cycle == 1) {
          critical = -dsu[0].par[dsu[0].Find(A)];
        } else {
          critical = 0;
        }
      }
    }
  } else {
    for (int i = 0; i < 4; ++i) {
      if (isCritical[i] && root[i] != A && root[i] != B) {
        deg[i][A]++;
        deg[i][B]++;
        if (!dsu[i].Union(A, B) || deg[i][A] >= 3 || deg[i][B] >= 3) {
          isCritical[i] = false;
          --critical;
        }
      }
    }
  }
}

int CountCritical() {
  return critical;
}

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