답안 #393053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393053	2021-04-22T15:45:38 Z	rainboy	낙하산 고리들 (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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-