Submission #589383

#	Time	Username	Problem	Language	Result	Execution time	Memory
589383		Virv	Parachute rings (IOI12_rings)	C++17	100 / 100	1647 ms	113852 KiB

rings

#include <numeric>
#include <vector>

struct DSU {
	std::vector<int> p, r;

	explicit DSU(int n) : p(n), r(n, 1) { iota(p.begin(), p.end(), 0); }

	int find(int i) { return i == p[i] ? i : p[i] = find(p[i]); }

	bool merge(int i, int j) {
		i = find(i);
		j = find(j);
		if (i == j) return false;
		if (r[i] > r[j]) std::swap(i, j);
		p[i] = j;
		r[j] += r[i];
		return true;
	}
};

struct World {
	std::vector<int> c;
	DSU				 dsu;
	int				 killed;

	explicit World(int n) : c(n), dsu(n), killed(-1) {}
};

static int							 n;
static std::vector<World>			 worlds;
static std::vector<std::vector<int>> g;
static bool							 many;
static int							 cyc;

void Init(int n) {
	::n = n;
	worlds.emplace_back(n);
	g.assign(n, {});
	many = false;
	cyc	 = -1;
}

void Link(int a, int b) {
	if (many) {
		for (int i = worlds.size(); i--;) {
			auto &[c, dsu, k] = worlds[i];
			if (a == k || b == k) continue;

			c[a] += 1;
			c[b] += 1;
			if (c[a] > 2 || c[b] > 2 || !dsu.merge(a, b)) {
				worlds[i] = std::move(worlds.back());
				worlds.pop_back();
			}
		}
	} else {
		auto &[c, dsu, _] = worlds[0];

		g[a].push_back(b);
		g[b].push_back(a);

		c[a] += 1;
		c[b] += 1;
		if (c[a] > 2 || c[b] > 2) {
			auto			 x	= c[a] > 2 ? a : b;
			std::vector<int> ks = g[x];
			ks.push_back(x);

			worlds.clear();
			many = true;

			for (auto k : ks) {
				worlds.emplace_back(n);
				worlds.back().killed = k;
			}

			for (int i = 0; i < n; ++i)
				for (auto j : g[i])
					if (i < j) Link(i, j);
			return;
		}

		if (!dsu.merge(a, b)) {
			if (cyc == -1) {
				cyc = a;
			} else {
				worlds.clear();
				many = true;
			}
			return;
		}
	}
}

int CountCritical() {
	if (many) {
		return worlds.size();
	} else {
		auto &[_, dsu, __] = worlds[0];
		return cyc != -1 ? dsu.r[dsu.find(cyc)] : n;
	}
}

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