Submission #393053

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393053	2021-04-22T15:45:38 Z	rainboy	Parachute rings (IOI12_rings)	C	20 / 100	3368 ms	224392 KB

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.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1100 KB	Output is correct
2	Correct	2249 ms	164084 KB	Output is correct
3	Correct	3353 ms	196036 KB	Output is correct
4	Correct	77 ms	16120 KB	Output is correct
5	Correct	1180 ms	94604 KB	Output is correct
6	Correct	3310 ms	196068 KB	Output is correct
7	Correct	372 ms	195992 KB	Output is correct
8	Correct	1809 ms	166260 KB	Output is correct
9	Correct	3300 ms	196036 KB	Output is correct
10	Correct	3220 ms	196072 KB	Output is correct

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	598 ms	224392 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1100 KB	Output is correct
2	Correct	2249 ms	164084 KB	Output is correct
3	Correct	3353 ms	196036 KB	Output is correct
4	Correct	77 ms	16120 KB	Output is correct
5	Correct	1180 ms	94604 KB	Output is correct
6	Correct	3310 ms	196068 KB	Output is correct
7	Correct	372 ms	195992 KB	Output is correct
8	Correct	1809 ms	166260 KB	Output is correct
9	Correct	3300 ms	196036 KB	Output is correct
10	Correct	3220 ms	196072 KB	Output is correct
11	Correct	3368 ms	196076 KB	Output is correct
12	Runtime error	185 ms	220216 KB	Execution killed with signal 11
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1100 KB	Output is correct
2	Correct	2249 ms	164084 KB	Output is correct
3	Correct	3353 ms	196036 KB	Output is correct
4	Correct	77 ms	16120 KB	Output is correct
5	Correct	1180 ms	94604 KB	Output is correct
6	Correct	3310 ms	196068 KB	Output is correct
7	Correct	372 ms	195992 KB	Output is correct
8	Correct	1809 ms	166260 KB	Output is correct
9	Correct	3300 ms	196036 KB	Output is correct
10	Correct	3220 ms	196072 KB	Output is correct
11	Correct	3368 ms	196076 KB	Output is correct
12	Runtime error	185 ms	220216 KB	Execution killed with signal 11
13	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1100 KB	Output is correct
2	Correct	2249 ms	164084 KB	Output is correct
3	Correct	3353 ms	196036 KB	Output is correct
4	Correct	77 ms	16120 KB	Output is correct
5	Correct	1180 ms	94604 KB	Output is correct
6	Correct	3310 ms	196068 KB	Output is correct
7	Correct	372 ms	195992 KB	Output is correct
8	Correct	1809 ms	166260 KB	Output is correct
9	Correct	3300 ms	196036 KB	Output is correct
10	Correct	3220 ms	196072 KB	Output is correct
11	Runtime error	598 ms	224392 KB	Execution killed with signal 11
12	Halted	0 ms	0 KB	-