Submission #223729

#	Time	Username	Problem	Language	Result	Execution time	Memory
223729		staniewzki	Parachute rings (IOI12_rings)	C++17	0 / 100	2642 ms	234744 KiB

rings

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
 
template<class T> int size(T && a) { return (int) a.size(); }

struct Graph {
	vector<vector<int>> adj;
	vector<int> rep;

	int find(int x) {
		return rep[x] < 0 ? x : find(rep[x]);
	}

	vector<int> bicomp;
	int get_cycle() {
		return -rep[find(bicomp[0])];
	}

	void join(int x, int y) {
		x = find(x), y = find(y);
		if(x == y) {
			bicomp.emplace_back(x);
			return;
		}
		rep[x] += rep[y];
		rep[y] = x;
	}

	int deg = 0;
	void add_edge(int a, int b) {
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
		deg = max(deg, size(adj[a]));
		deg = max(deg, size(adj[b]));
		join(a, b);
	}

	Graph(int n = 0) : adj(n), rep(n, -1) {}
};

int n;
Graph graph;
vector<Graph> without;

void Init(int N) {
	n = N;
	graph = Graph(n);
}

void Link(int A, int B) {
	if(graph.deg < 3) {
		graph.add_edge(A, B);
		if(graph.deg == 3) {
			if(size(graph.adj[A]) != 3)
				swap(A, B);

			vector<int> crit = {A};
			for(int u : graph.adj[A])
				crit.emplace_back(u);

			for(int x : crit) {
				without.emplace_back(n);
				auto &g = without.back();
				
				REP(v, n) for(int u : graph.adj[v]) {
					if(u < v && v != x && u != x)
						g.add_edge(v, u);		
				}
			}
		}
	}
	else {
		for(auto &g : without)
			g.add_edge(A, B);
	}
}

int CountCritical() {
	if(graph.deg < 3) {
		int bc = size(graph.bicomp);
		if(bc == 0) return n;
		if(bc == 1) return graph.get_cycle();
		return 0;
	}
	else {
		int ret = 0;
		for(auto &g : without) {
			if(size(g.bicomp) == 0 && g.deg < 3)
				ret++;
		}
		return ret;
	}
}

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