Submission #1147989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147989		iah	Parachute rings (IOI12_rings)	C++20	0 / 100	568 ms	58304 KiB

rings

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

#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())

const int nmax = 1e6;

int n, deg[nmax + 7], st, en, par[nmax + 7];
bool ok[nmax + 7], vis[nmax + 7], four, found_cycle = 0;
vector < int > ans, adj[nmax + 7];

struct DSU {
  int sz[nmax + 7], par[nmax + 7];
  void init(int n) {
    iota(par, par + n, 0);
    REP(i, n) {
      sz[i] = 1;
    }
  }

  int find_par(int i) {
    return (par[i] == i ? i : par[i] = find_par(par[i]));
  }

  bool unite(int u, int v) {
    u = find_par(u);
    v = find_par(v);

    if (u == v) {
      return 0;
    }

    if (sz[u] < sz[v]) {
      swap(u, v);
    }

    par[v] = u;
    sz[u] += sz[v];
    return 1;
  }
}dsu;

void Init(int N_) {
  n = N_;
  ans.resize(n);
  iota(ans.begin(), ans.end(), 0);

  dsu.init(n);
}

void dfs(int i, int j) {
  vis[i] = 1;

  for (auto x: adj[i]) {
    if (x == j) {
      continue;
    }

    if (vis[x]) {
      en = x;
      st = i;
      continue;
    }

    par[x] = i;
    dfs(x, i);
  }
}

vector < int > find_cycle() {
  REP(i, n) {
    if (!vis[i]) {
      dfs(i, -1);
    }
  }

//  REP(i, n) {
//    cout << vis[i] << " " << par[i] << "\n";
//  }
//  cout << st << " " << en << "\n";

  vector < int > cycle;
  while (en != st) {
    cerr << en << "\n";
    cycle.push_back(en);
    en = par[en];
  }
  cycle.push_back(en);
  return move(cycle);
}

void Link(int A, int B) {
  if (ans.empty()) {
    return;
  }
  adj[A].push_back(B);
  adj[B].push_back(A);

  if (!dsu.unite(A, B)) {
    if (!found_cycle) {
      found_cycle = 1;
      vector < int > cycle = find_cycle();
      for (auto x: ans) {
        ok[x] = 1;
      }
      vector < int > ().swap(ans);

      for (auto x: cycle) {
        if (ok[x]) {
          ans.push_back(x);
        }
      }

      REP(i, n) {
        ok[i] = 0;
      }
    }
  }

  for (auto x: {A, B}) {
    if (sz(adj[x]) == 4) {
      if (four) {
        vector < int > ().swap(ans);
        return;
      }
      else {
        bool ok = 0;
        for (auto i: ans) {
          if (i == x) {
            ok = 1;
          }
        }
        if (ok) {
          ans.push_back(x);
        }
      }
    }

    if (sz(adj[x]) == 3) {
      for (auto i: adj[x]) {
        ok[i] = 1;
      }
      ok[x] = 1;

      for (auto &x: ans) {
        if (!ok[x]) {
          x = -1;
        }
      }
      sort(ans.begin(), ans.end(), greater < int > ());
      while (!ans.empty() && ans.back() == -1) {
        ans.pop_back();
      }

      for (auto i: adj[x]) {
        ok[i] = 0;
      }
      ok[x] = 0;
    }
  }
}

int CountCritical() {
  return sz(ans);

}

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