Submission #1147997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147997		iah	Parachute rings (IOI12_rings)	C++20	37 / 100	1014 ms	104800 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, st = 0, en = 0, par[nmax + 7];
bool ok[nmax + 7], vis[nmax + 7], four, found_cycle = 0, fc;
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);
  REP(i, n) {
    adj[i].push_back(i);
  }

  dsu.init(n);
}

void dfs(int i, int j) {
//  cout << "dfs " << j << " " << i << "\n";
  vis[i] = 1;

  for (auto x: adj[i]) {
    if (en || st) {
      break;
    }

//    cout << "edge " << i << " " << x << "\n";

    if (x == j || x == i) {
      continue;
    }

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

    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 add(vector < int > &vec) {
//  cout << "add ";
//  for (auto x: vec) {
//    cout << x << " ";
//  }
//  cout << "\n";

  for (auto x: vec) {
    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 x: vec) {
    ok[x] = 0;
  }
}

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();
      add(cycle);
    }
    else if (!fc) {
      if (dsu.find_par(ans[0]) != dsu.find_par(A)) {
        vector < int > ().swap(ans);
        return;
      }

      fc = 1;

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

      REP(i, n) {
        add(adj[i]);
      }
    }
  }

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

    if (sz(adj[x]) == 4) {
      add(adj[x]);
    }
  }

//  cout << "link " << A << " " << B << "\n";
//  for (auto x: ans) {
//    cout << x << " ";
//  }
//  cout << "\n";
}

int CountCritical() {
//  for (auto x: ans) {
//    cout << x << " ";
//  }
//  cout << "\n";

  return sz(ans);

}

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