oj.uz

답안 #536552

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
536552 2022-03-13T14:00:47 Z rainboy 전압 (JOI14_voltage) C
10 / 100
 1000 ms 4092 KB 
#include <stdio.h>
#include <string.h>

#define N	100000
#define M	200000

int ds[N * 2];

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

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

int main() {
	static int ii[M], jj[M];
	int n, m, h, h_, i, j, cnt;

	scanf("%d%d", &n, &m);
	for (h = 0; h < m; h++)
		scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
	cnt = 0;
	for (h = 0; h < m; h++) {
		memset(ds, -1, n * 2 * sizeof *ds);
		for (h_ = 0; h_ < m; h_++) {
			i = ii[h_], j = jj[h_];
			if (h_ == h)
				join(i << 1 | 0, j << 1 | 0), join(i << 1 | 1, j << 1 | 1);
			else
				join(i << 1 | 0, j << 1 | 1), join(i << 1 | 1, j << 1 | 0);
		}
		cnt++;
		for (i = 0; i < n; i++)
			if (find(i << 1 | 0) == find(i << 1 | 1)) {
				cnt--;
				break;
			}
	}
	printf("%d\n", cnt);
	return 0;
}

Compilation message

voltage.c: In function 'main':
voltage.c:31:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
voltage.c:33:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 308 KB Output is correct
2 Correct 58 ms 320 KB Output is correct
3 Correct 53 ms 340 KB Output is correct
4 Correct 22 ms 316 KB Output is correct
5 Correct 75 ms 212 KB Output is correct
6 Correct 85 ms 340 KB Output is correct
7 Correct 83 ms 320 KB Output is correct
8 Correct 77 ms 316 KB Output is correct
9 Correct 60 ms 320 KB Output is correct
10 Correct 81 ms 320 KB Output is correct
11 Correct 83 ms 312 KB Output is correct
12 Correct 79 ms 320 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1058 ms 2916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1090 ms 2508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1082 ms 4092 KB Time limit exceeded
2 Halted 0 ms 0 KB -