oj.uz

Submission #887626

# Submission time Handle Problem Language Result Execution time Memory
887626 2023-12-14T21:10:18 Z rainboy Sleepy game (innopolis2018_final_D) C
100 / 100
 35 ms 13556 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	100000

int *ej[N], eo[N];
int qu[N * 2], cnt; char visited[N * 2];

int dfs1(int i) {
	int o;

	qu[cnt++] = i;
	if (visited[i << 1 | cnt % 2]) {
		cnt--;
		return 0;
	}
	if (eo[i] == 0 && cnt % 2 == 0)
		return 1;
	visited[i << 1 | cnt % 2] = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (dfs1(j))
			return 1;
	}
	cnt--;
	return 0;
}

int dfs2(int i) {
	int o;

	if (visited[i])
		return visited[i] == -1;
	visited[i] = -1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (dfs2(j))
			return 1;
	}
	visited[i] = 1;
	return 0;
}

int main() {
	int n, m, h, i, o;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%d", &eo[i]);
		ej[i] = (int *) malloc(eo[i] * sizeof *ej[i]);
		for (o = eo[i]; o--; )
			scanf("%d", &ej[i][o]), ej[i][o]--;
	}
	scanf("%d", &i), i--;
	if (dfs1(i)) {
		printf("Win\n");
		for (h = 0; h < cnt; h++)
			printf("%d ", qu[h] + 1);
		printf("\n");
	} else {
		memset(visited, 0, n * sizeof *visited);
		printf(dfs2(i) ? "Draw\n" : "Lose\n");
	}
	return 0;
}

Compilation message

D.c: In function 'main':
D.c:50:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
D.c:52:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d", &eo[i]);
      |   ^~~~~~~~~~~~~~~~~~~
D.c:55:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |    scanf("%d", &ej[i][o]), ej[i][o]--;
      |    ^~~~~~~~~~~~~~~~~~~~~~
D.c:57:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d", &i), i--;
      |  ^~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct solution.
2 Correct 0 ms 348 KB Correct solution.
3 Correct 0 ms 348 KB Correct solution.
4 Correct 22 ms 9552 KB Correct solution.
5 Correct 13 ms 5464 KB Correct solution.
6 Correct 21 ms 8028 KB Correct solution.
7 Correct 29 ms 11208 KB Correct solution.
8 Correct 31 ms 13556 KB Correct solution.
9 Correct 26 ms 10588 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct solution.
2 Correct 0 ms 348 KB Correct solution.
3 Correct 0 ms 344 KB Correct solution.
4 Correct 24 ms 6024 KB Correct solution.
5 Correct 0 ms 348 KB Correct solution.
6 Correct 3 ms 1224 KB Correct solution.
7 Correct 35 ms 9044 KB Correct solution.
8 Correct 29 ms 8892 KB Correct solution.

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 424 KB Correct solution.
2 Correct 1 ms 344 KB Correct solution.
3 Correct 0 ms 348 KB Correct solution.
4 Correct 0 ms 348 KB Correct solution.
5 Correct 0 ms 348 KB Correct solution.
6 Correct 1 ms 440 KB Correct solution.
7 Correct 1 ms 348 KB Correct solution.
8 Correct 1 ms 348 KB Correct solution.
9 Correct 1 ms 344 KB Correct solution.
10 Correct 1 ms 428 KB Correct solution.
11 Correct 1 ms 348 KB Correct solution.

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 424 KB Correct solution.
2 Correct 1 ms 344 KB Correct solution.
3 Correct 0 ms 348 KB Correct solution.
4 Correct 0 ms 348 KB Correct solution.
5 Correct 0 ms 348 KB Correct solution.
6 Correct 1 ms 440 KB Correct solution.
7 Correct 1 ms 348 KB Correct solution.
8 Correct 1 ms 348 KB Correct solution.
9 Correct 1 ms 344 KB Correct solution.
10 Correct 1 ms 428 KB Correct solution.
11 Correct 1 ms 348 KB Correct solution.
12 Correct 13 ms 2136 KB Correct solution.
13 Correct 17 ms 2648 KB Correct solution.
14 Correct 21 ms 2384 KB Correct solution.
15 Correct 16 ms 2096 KB Correct solution.
16 Correct 15 ms 2336 KB Correct solution.
17 Correct 1 ms 860 KB Correct solution.
18 Correct 15 ms 2468 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct solution.
2 Correct 0 ms 348 KB Correct solution.
3 Correct 0 ms 348 KB Correct solution.
4 Correct 22 ms 9552 KB Correct solution.
5 Correct 13 ms 5464 KB Correct solution.
6 Correct 21 ms 8028 KB Correct solution.
7 Correct 29 ms 11208 KB Correct solution.
8 Correct 31 ms 13556 KB Correct solution.
9 Correct 26 ms 10588 KB Correct solution.
10 Correct 0 ms 348 KB Correct solution.
11 Correct 0 ms 348 KB Correct solution.
12 Correct 0 ms 344 KB Correct solution.
13 Correct 24 ms 6024 KB Correct solution.
14 Correct 0 ms 348 KB Correct solution.
15 Correct 3 ms 1224 KB Correct solution.
16 Correct 35 ms 9044 KB Correct solution.
17 Correct 29 ms 8892 KB Correct solution.
18 Correct 1 ms 424 KB Correct solution.
19 Correct 1 ms 344 KB Correct solution.
20 Correct 0 ms 348 KB Correct solution.
21 Correct 0 ms 348 KB Correct solution.
22 Correct 0 ms 348 KB Correct solution.
23 Correct 1 ms 440 KB Correct solution.
24 Correct 1 ms 348 KB Correct solution.
25 Correct 1 ms 348 KB Correct solution.
26 Correct 1 ms 344 KB Correct solution.
27 Correct 1 ms 428 KB Correct solution.
28 Correct 1 ms 348 KB Correct solution.
29 Correct 13 ms 2136 KB Correct solution.
30 Correct 17 ms 2648 KB Correct solution.
31 Correct 21 ms 2384 KB Correct solution.
32 Correct 16 ms 2096 KB Correct solution.
33 Correct 15 ms 2336 KB Correct solution.
34 Correct 1 ms 860 KB Correct solution.
35 Correct 15 ms 2468 KB Correct solution.
36 Correct 22 ms 4952 KB Correct solution.
37 Correct 24 ms 5928 KB Correct solution.
38 Correct 34 ms 9044 KB Correct solution.
39 Correct 24 ms 6316 KB Correct solution.
40 Correct 34 ms 6312 KB Correct solution.
41 Correct 25 ms 10588 KB Correct solution.
42 Correct 30 ms 8788 KB Correct solution.