Submission #1042932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042932		pawned	Parachute rings (IOI12_rings)	C++17	55 / 100	4040 ms	123304 KiB

rings

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const int MAX = 1000005;

struct DSU {
	vi e;
	DSU(int N) {
		e = vi(N, -1);
	}
	int root(int x) {
		if (e[x] < 0) {
			return x;
		}
		else {
			e[x] = root(e[x]);
			return e[x];
		}
	}
	bool sameset(int x, int y) {
		return (root(x) == root(y));
	}
	bool unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y)
			return false;
		if (-e[x] < -e[y])
			swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return true;
	}
	int size(int x) {
		return -e[root(x)];
	}
};

int N;

vi adj[MAX];

void Init(int N_) {
	N = N_;
}

void Link(int A, int B) {
	adj[A].pb(B);
	adj[B].pb(A);
}

int CountCritical() {
	vi sus;
	for (int i = 0; i < N; i++) {
		if (adj[i].size() >= 3) {
			sus.pb(i);
			if (adj[i].size() == 3) {
				for (int x : adj[i])
					sus.pb(x);
			}
			break;
		}
	}
	if ((int)(sus.size()) > 0) {
		int total = 0;
		for (int i : sus) {
			// try removing each vertex, make new adj
			// to check, ensure no adj cnt is > 2
			// and N - edge_cnt equals number of ccs
			// removed link is a chain itself
			vi adjc[N];
			int cnt = 0;
			for (int j = 0; j < N; j++) {
				if (j == i)
					continue;
				for (int k : adj[j]) {
					if (k != i) {
						adjc[j].pb(k);
						cnt++;
					}
				}
			}
			cnt /= 2;
			int maxc = 0;
			for (int j = 0; j < N; j++) {
				maxc = max(maxc, (int)(adjc[j].size()));
			}
//			cout<<"cnt, maxc: "<<cnt<<" "<<maxc<<endl;
			int ccs = 0;
			vector<bool> vis(N, false);
			for (int j = 0; j < N; j++) {
				if (!vis[j]) {
					ccs++;
					queue<int> q;
					q.push(j);
					vis[j] = true;
					while (!q.empty()) {
						int x = q.front();
						q.pop();
						for (int y : adjc[x]) {
							if (!vis[y]) {
								q.push(y);
								vis[y] = true;
							}
						}
					}
				}
			}
//			cout<<"ccs: "<<ccs<<endl;
			if ((maxc <= 2) && (N - cnt == ccs))
				total++;
		}
		return total;
	}
	else {	// all vertices have degree <= 2
		// all lines or cycles
		int cnt = 0;
		for (int j = 0; j < N; j++) {
			cnt += (int)(adj[j].size());
		}
		cnt /= 2;
		int ccs = 0;
		vector<bool> vis(N, false);
		for (int j = 0; j < N; j++) {
			if (!vis[j]) {
				ccs++;
				queue<int> q;
				q.push(j);
				vis[j] = true;
				while (!q.empty()) {
					int x = q.front();
					q.pop();
					for (int y : adj[x]) {
						if (!vis[y]) {
							q.push(y);
							vis[y] = true;
						}
					}
				}
			}
		}
		if (N - cnt == ccs) {
			return N;
		}
		else if (N - cnt == ccs - 1) {	// one cycle, find length
			// given adjacency list, find the cycle
			// find all components, then find # edges in comp
			DSU dsu(N);
			for (int i = 0; i < N; i++) {
				for (int j : adj[i])
					dsu.unite(i, j);
			}
			vector<vi> incomp(N);	// N vectors
			for (int i = 0; i < N; i++) {
				incomp[dsu.root(i)].pb(i);
			}
			int ans = -1;
			for (int i = 0; i < N; i++) {
				if ((int)(incomp[i].size()) != 0) {
					int sumd = 0;
					for (int j : incomp[i])
						sumd += (int)(adj[j].size());
					if (sumd / 2 == (int)(incomp[i].size())) {
						ans = sumd / 2;
						break;
					}
				}
			}
			return ans;
		}
		else {
			return 0;
		}
	}
}

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