Submission #120739

#	Time	Username	Problem	Language	Result	Execution time	Memory
120739		MAMBA	Parachute rings (IOI12_rings)	C++17	100 / 100	3928 ms	131688 KiB

rings

#include <bits/stdc++.h>

using namespace std;

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back

constexpr int MAXN = 1e6 + 10;

struct dsu {
  int par[MAXN], sz[MAXN];
  dsu() {
    iota(par, par + MAXN, 0);
    fill(sz, sz + MAXN, 1);
  }
  int getPar(int v) { return par[v] == v ? v : par[v] = getPar(par[v]); }
  int merge(int u, int v) {
    v = getPar(v), u = getPar(u);
    if (v == u) return sz[v];
    par[v] = u;
    sz[u] += sz[v];
    return -1;
  }
} ds[5];

int N, tmp, deg[5][MAXN];
vector<int> adj[MAXN];
bool flag, can[5];

void Init(int N_) {
  N = N_;
  tmp = 0;
  flag = false;
  memset(can, true, sizeof(can));
  memset(deg, 0, sizeof(deg));
  rep(i, 0, 5) ds[i] = dsu();
  rep(i, 0, N) adj[i].clear();
}

int bad[5];

inline void Link(int A, int B, int id) {
  if (bad[id] == A || bad[id] == B) return;
  deg[id][A]++, deg[id][B]++;
  if (deg[id][A] == 3 || deg[id][B] == 3) can[id] = false;
  if (~ds[id].merge(A, B)) can[id] = false;
}

inline void build(int v) {
  flag = true;
  bad[1] = v;
  rep(i, 0, 3) bad[2 + i] = adj[v][i];
  rep(i, 0, N) for (auto e : adj[i]) if (e > i) rep(z, 1, 5) Link(i, e, z);
}

void Link(int A, int B) {
  adj[A].pb(B);
  adj[B].pb(A);
  if (!flag && adj[A].size() == 3) return build(A), void();
  if (!flag && adj[B].size() == 3) return build(B), void();
  if (!flag) {
    int me = ds[0].merge(A, B);
    if (~me) {
      if (!tmp)
        tmp = me;
      else
        tmp = -1;
    }
  } else
    rep(i, 1, 5) Link(A, B, i);
}

int CountCritical() {
  if (!flag) {
    if (!tmp) return N;
    if (~tmp) return tmp;
    return 0;
  }
  int res = 0;
  rep(i, 1, 5) res += can[i];
  return res;
}

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