oj.uz

답안 #544617

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
544617 2022-04-02T13:38:02 Z rainboy 어르신 집배원 (BOI14_postmen) C
100 / 100
 374 ms 68016 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	500000
#define M	500000

int ij[M]; char used[M];
int *oh[N], oo[N];

void link(int i, int h) {
	int o = oo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		oh[i] = (int *) realloc(oh[i], o * 2 * sizeof *oh[i]);
	oh[i][o] = h;
}

int qu[1 + M], cnt;

void dfs(int i) {
	while (oo[i]) {
		int h = oh[i][--oo[i]];

		if (!used[h])
			used[h] = 1, dfs(i ^ ij[h]);
	}
	qu[cnt++] = i;
}

int main() {
	static char in[N];
	int n, m, h, i, j, cnt_;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		oh[i] = (int *) malloc(2 * sizeof *oh[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		ij[h] = i ^ j;
		link(i, h), link(j, h);
	}
	dfs(0);
	cnt_ = 0;
	for (h = 0; h < cnt; h++)
		if (!in[qu[h]])
			in[qu[h]] = 1, qu[cnt_++] = qu[h];
		else {
			while (qu[cnt_ - 1] != qu[h]) {
				printf("%d ", qu[cnt_ - 1] + 1);
				in[qu[--cnt_]] = 0;
			}
			printf("%d\n", qu[h] + 1);
		}
	return 0;
}

Compilation message

postmen.c: In function 'link':
postmen.c:13:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   13 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
postmen.c: In function 'main':
postmen.c:34:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
postmen.c:38:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 564 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 6 ms 1748 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 34 ms 9548 KB Output is correct
10 Correct 2 ms 568 KB Output is correct
11 Correct 2 ms 564 KB Output is correct
12 Correct 37 ms 9956 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 428 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 5 ms 1752 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 33 ms 9504 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 37 ms 9948 KB Output is correct
13 Correct 45 ms 13512 KB Output is correct
14 Correct 47 ms 9292 KB Output is correct
15 Correct 45 ms 12044 KB Output is correct
16 Correct 43 ms 13540 KB Output is correct
17 Correct 47 ms 6652 KB Output is correct
18 Correct 43 ms 10816 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 656 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 6 ms 1752 KB Output is correct
8 Correct 1 ms 552 KB Output is correct
9 Correct 34 ms 9576 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 36 ms 9920 KB Output is correct
13 Correct 43 ms 13556 KB Output is correct
14 Correct 41 ms 9280 KB Output is correct
15 Correct 41 ms 12072 KB Output is correct
16 Correct 43 ms 13516 KB Output is correct
17 Correct 46 ms 6628 KB Output is correct
18 Correct 46 ms 10828 KB Output is correct
19 Correct 300 ms 68016 KB Output is correct
20 Correct 309 ms 46764 KB Output is correct
21 Correct 301 ms 59644 KB Output is correct
22 Correct 296 ms 67968 KB Output is correct
23 Correct 170 ms 46156 KB Output is correct
24 Correct 374 ms 33284 KB Output is correct
25 Correct 309 ms 54296 KB Output is correct