oj.uz

Submission #282870

# Submission time Handle Problem Language Result Execution time Memory
282870 2020-08-25T05:47:39 Z 송준혁(#5748) Sleepy game (innopolis2018_final_D) C++17
100 / 100
 96 ms 13560 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, S;
vector<int> adj[101010];
int P[202020];
bool D[202020], cyc[202020], chk[202020], vis[202020];

void dfs(int u){
	if (vis[u]) return;
	if (u > N && adj[u-N].empty()){
		D[u] = 1;
		return;
	}
	vis[u] = chk[u] = true;
	if (u > N){
		for (int v : adj[u-N]){
			dfs(v);
			if (!D[u] && D[v]) D[u] = true, P[u] = v;
			if (chk[v] || cyc[v]) cyc[u] = true;
		}
	}
	else{
		for (int v : adj[u]){
			dfs(v+N);
			if (!D[u] && D[v+N]) D[u] = true, P[u] = v+N;
			if (chk[v+N] || cyc[v+N]) cyc[u] = true;
		}
	}
	chk[u] = false;
}

int main(){
	scanf("%d %*d", &N);
	for (int i=1; i<=N; i++){
		scanf("%d", &M);
		for (int j=1; j<=M; j++){
			int x;
			scanf("%d", &x);
			adj[i].push_back(x);
		}
	}
	scanf("%d", &S);
	dfs(S);
	if (D[S]){
		puts("Win");
		for (int u=S; u; u=P[u]){
			if (u>N) printf("%d ", u-N);
			else printf("%d ", u);
		}
		printf("\n");
	}
	else if (cyc[S]) puts("Draw");
	else puts("Lose");
	return 0;
}

Compilation message

D.cpp: In function 'int main()':
D.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |  scanf("%d %*d", &N);
      |  ~~~~~^~~~~~~~~~~~~~
D.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |   scanf("%d", &M);
      |   ~~~~~^~~~~~~~~~
D.cpp:41:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~
D.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |  scanf("%d", &S);
      |  ~~~~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 3 ms 2688 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 49 ms 9848 KB Correct solution.
5 Correct 27 ms 6776 KB Correct solution.
6 Correct 38 ms 7928 KB Correct solution.
7 Correct 69 ms 12792 KB Correct solution.
8 Correct 67 ms 13560 KB Correct solution.
9 Correct 54 ms 11256 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 2 ms 2688 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 57 ms 5752 KB Correct solution.
5 Correct 2 ms 2688 KB Correct solution.
6 Correct 9 ms 3456 KB Correct solution.
7 Correct 84 ms 10104 KB Correct solution.
8 Correct 68 ms 10228 KB Correct solution.

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 3 ms 2816 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 2 ms 2688 KB Correct solution.
5 Correct 3 ms 2688 KB Correct solution.
6 Correct 3 ms 2816 KB Correct solution.
7 Correct 3 ms 2816 KB Correct solution.
8 Correct 3 ms 2816 KB Correct solution.
9 Correct 3 ms 2688 KB Correct solution.
10 Correct 3 ms 2816 KB Correct solution.
11 Correct 3 ms 2816 KB Correct solution.

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 3 ms 2816 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 2 ms 2688 KB Correct solution.
5 Correct 3 ms 2688 KB Correct solution.
6 Correct 3 ms 2816 KB Correct solution.
7 Correct 3 ms 2816 KB Correct solution.
8 Correct 3 ms 2816 KB Correct solution.
9 Correct 3 ms 2688 KB Correct solution.
10 Correct 3 ms 2816 KB Correct solution.
11 Correct 3 ms 2816 KB Correct solution.
12 Correct 31 ms 4736 KB Correct solution.
13 Correct 37 ms 4992 KB Correct solution.
14 Correct 34 ms 4600 KB Correct solution.
15 Correct 37 ms 4600 KB Correct solution.
16 Correct 34 ms 4600 KB Correct solution.
17 Correct 4 ms 3200 KB Correct solution.
18 Correct 32 ms 4728 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 3 ms 2688 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 49 ms 9848 KB Correct solution.
5 Correct 27 ms 6776 KB Correct solution.
6 Correct 38 ms 7928 KB Correct solution.
7 Correct 69 ms 12792 KB Correct solution.
8 Correct 67 ms 13560 KB Correct solution.
9 Correct 54 ms 11256 KB Correct solution.
10 Correct 2 ms 2688 KB Correct solution.
11 Correct 2 ms 2688 KB Correct solution.
12 Correct 2 ms 2688 KB Correct solution.
13 Correct 57 ms 5752 KB Correct solution.
14 Correct 2 ms 2688 KB Correct solution.
15 Correct 9 ms 3456 KB Correct solution.
16 Correct 84 ms 10104 KB Correct solution.
17 Correct 68 ms 10228 KB Correct solution.
18 Correct 2 ms 2688 KB Correct solution.
19 Correct 3 ms 2816 KB Correct solution.
20 Correct 2 ms 2688 KB Correct solution.
21 Correct 2 ms 2688 KB Correct solution.
22 Correct 3 ms 2688 KB Correct solution.
23 Correct 3 ms 2816 KB Correct solution.
24 Correct 3 ms 2816 KB Correct solution.
25 Correct 3 ms 2816 KB Correct solution.
26 Correct 3 ms 2688 KB Correct solution.
27 Correct 3 ms 2816 KB Correct solution.
28 Correct 3 ms 2816 KB Correct solution.
29 Correct 31 ms 4736 KB Correct solution.
30 Correct 37 ms 4992 KB Correct solution.
31 Correct 34 ms 4600 KB Correct solution.
32 Correct 37 ms 4600 KB Correct solution.
33 Correct 34 ms 4600 KB Correct solution.
34 Correct 4 ms 3200 KB Correct solution.
35 Correct 32 ms 4728 KB Correct solution.
36 Correct 72 ms 9216 KB Correct solution.
37 Correct 84 ms 10104 KB Correct solution.
38 Correct 82 ms 10488 KB Correct solution.
39 Correct 96 ms 8056 KB Correct solution.
40 Correct 88 ms 7032 KB Correct solution.
41 Correct 57 ms 11684 KB Correct solution.
42 Correct 66 ms 9208 KB Correct solution.