제출 #393066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393066		rainboy	낙하산 고리들 (IOI12_rings)	C11	100 / 100	1048 ms	63288 KiB

rings

#include <string.h>

#define N	1000000
#define M	1000000

int find(int *ds, int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds, ds[i]));
}

int join(int *ds, int i, int j) {
	i = find(ds, i);
	j = find(ds, j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}

char critical[4]; int uu[4], ds[4][N], dd[4][N], adj[N][3], ii[M], jj[M], n, m, cnt, mode;

void Init(int n_) {
	n = n_, cnt = n, mode = 0;
	memset(ds[0], -1, n * sizeof *ds[0]);
}

void mode1(int i) {
	int j;

	mode = 1, cnt = 0;
	for (j = 0; j < n; j++)
		if (find(ds[0], j) == find(ds[0], i))
			cnt++;
}

void mode2(int i) {
	int h;

	mode = 2;
	for (h = 0; h < 4; h++) {
		uu[h] = h < 3 ? adj[i][h] : i, critical[h] = 1;
		memset(ds[h], -1, n * sizeof *ds[h]);
		memset(dd[h], 0, n * sizeof *dd[h]);
	}
	while (m--) {
		int i = ii[m], j = jj[m];

		for (h = 0; h < 4; h++) {
			int u = uu[h];

			if (i == u || j == u)
				continue;
			if (++dd[h][i] > 2)
				critical[h] = 0;
			if (++dd[h][j] > 2)
				critical[h] = 0;
			if (!join(ds[h], i, j))
				critical[h] = 0;
		}
	}
}

void mode3() {
	mode = 3, cnt = 0;
}

void Link(int i, int j) {
	if (mode <= 1) {
		ii[m] = i, jj[m] = j, m++;
		adj[i][dd[0][i]++] = j, adj[j][dd[0][j]++] = i;
		if (dd[0][i] > 2)
			mode2(i);
		else if (dd[0][j] > 2)
			mode2(j);
		else if (!join(ds[0], i, j)) {
			if (mode == 0)
				mode1(i);
			else
				mode3();
		}
	} else if (mode == 2) {
		int h;

		for (h = 0; h < 4; h++) {
			int u = uu[h];

			if (i == u || j == u)
				continue;
			if (++dd[h][i] > 2)
				critical[h] = 0;
			if (++dd[h][j] > 2)
				critical[h] = 0;
			if (!join(ds[h], i, j))
				critical[h] = 0;
		}
	}
}

int CountCritical() {
	if (mode == 2) {
		int h;

		cnt = 0;
		for (h = 0; h < 4; h++)
			if (critical[h])
				cnt++;
	}
	return cnt;
}

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