Submission #393053

#	Time	Username	Problem	Language	Result	Execution time	Memory
393053		rainboy	Parachute rings (IOI12_rings)	C11	20 / 100	3368 ms	224392 KiB

rings

#include <string.h>

#define N	5000

char critical[N];
int ii[N], ds[N][N], dd[N][N];

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;
}

int n;

void Init(int n_) {
	int i;

  n = n_;
	for (i = 0; i < n; i++) {
		ii[i] = i;
		memset(ds[i], -1, n * sizeof *ds[i]);
		critical[i] = 1;
	}
}

void Link(int i, int j) {
	int u;

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

int CountCritical() {
	int i, cnt;

	cnt = 0;
	for (i = 0; i < n; i++)
		if (critical[i])
			cnt++;
  return cnt;
}

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