Submission #887626

#	Time	Username	Problem	Language	Result	Execution time	Memory
887626		rainboy	Sleepy game (innopolis2018_final_D)	C11	100 / 100	35 ms	13556 KiB

D

#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 (stderr)

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 / 17
• Subtask 2: 19 / 19
• Subtask 3: 15 / 15
• Subtask 4: 11 / 11
• Subtask 5: 38 / 38