oj.uz

Submission #393065

# Submission time Handle Problem Language Result Execution time Memory
393065 2021-04-22T16:02:04 Z rainboy Parachute rings (IOI12_rings) C
0 / 100
 868 ms 55996 KB 
#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) == 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 4 ms 636 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 21208 KB Output is correct
2 Correct 754 ms 47560 KB Output is correct
3 Correct 868 ms 55996 KB Output is correct
4 Incorrect 576 ms 41044 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 4 ms 636 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 4 ms 636 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 4 ms 636 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -