oj.uz

Submission #113262

# Submission time Handle Problem Language Result Execution time Memory
113262 2019-05-24T13:22:58 Z 김세빈(#2857) Sleepy game (innopolis2018_final_D) C++14
100 / 100
 198 ms 21240 KB 
#include <bits/stdc++.h>

using namespace std;

vector <int> V1[202020], V2[101010];
queue <int> Q;
int P[202020];
bool chk[202020], sib[202020], fin[202020];
int n, m, s;

void dfs(int p)
{
	sib[p] = 1;
	
	for(int &t: V2[p]){
		if(!sib[t]){
			dfs(t);
		}
		else if(!fin[t]){
			printf("Draw\n");
			exit(0);
		}
	}
	
	fin[p] = 1;
}

int main()
{
	int i, a, b, p;
	
	scanf("%d%d", &n, &m);
	
	for(i=1; i<=n; i++){
		scanf("%d", &a);
		
		if(a == 0){
			chk[i - 1 << 1 | 1] = 1; P[i - 1 << 1 | 1] = -1;
			Q.push(i - 1 << 1 | 1);
		}
		
		for(; a--; ){
			scanf("%d", &b);
			V1[b - 1 << 1].push_back(i - 1 << 1 | 1);
			V1[b - 1 << 1 | 1].push_back(i - 1 << 1);
			V2[i].push_back(b);
		}
	}
	
	scanf("%d", &s);
	
	for(; !Q.empty(); ){
		p = Q.front(); Q.pop();
		for(int &t: V1[p]){
			if(!chk[t]){
				chk[t] = 1; P[t] = p;
				Q.push(t);
			}
		}
	}
	
	if(chk[s - 1 << 1]){
		printf("Win\n");
		for(i = s - 1 << 1; i != -1; i = P[i]){
			printf("%d ", (i >> 1) + 1);
		}
		printf("\n");
	}
	else{
		dfs(s);
		printf("Lose\n");
	}
	
	return 0;
}

Compilation message

D.cpp: In function 'int main()':
D.cpp:38:10: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    chk[i - 1 << 1 | 1] = 1; P[i - 1 << 1 | 1] = -1;
        ~~^~~
D.cpp:38:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    chk[i - 1 << 1 | 1] = 1; P[i - 1 << 1 | 1] = -1;
                               ~~^~~
D.cpp:39:13: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    Q.push(i - 1 << 1 | 1);
           ~~^~~
D.cpp:44:9: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    V1[b - 1 << 1].push_back(i - 1 << 1 | 1);
       ~~^~~
D.cpp:44:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    V1[b - 1 << 1].push_back(i - 1 << 1 | 1);
                             ~~^~~
D.cpp:45:9: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    V1[b - 1 << 1 | 1].push_back(i - 1 << 1);
       ~~^~~
D.cpp:45:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    V1[b - 1 << 1 | 1].push_back(i - 1 << 1);
                                 ~~^~~
D.cpp:62:11: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  if(chk[s - 1 << 1]){
         ~~^~~
D.cpp:64:13: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   for(i = s - 1 << 1; i != -1; i = P[i]){
           ~~^~~
D.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
D.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
D.cpp:43:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &b);
    ~~~~~^~~~~~~~~~
D.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &s);
  ~~~~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7424 KB Correct solution.
2 Correct 7 ms 7424 KB Correct solution.
3 Correct 7 ms 7424 KB Correct solution.
4 Correct 70 ms 17404 KB Correct solution.
5 Correct 59 ms 14456 KB Correct solution.
6 Correct 91 ms 17144 KB Correct solution.
7 Correct 116 ms 19192 KB Correct solution.
8 Correct 124 ms 20940 KB Correct solution.
9 Correct 103 ms 20824 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Correct solution.
2 Correct 9 ms 7424 KB Correct solution.
3 Correct 7 ms 7424 KB Correct solution.
4 Correct 150 ms 16352 KB Correct solution.
5 Correct 7 ms 7424 KB Correct solution.
6 Correct 16 ms 8576 KB Correct solution.
7 Correct 181 ms 18584 KB Correct solution.
8 Correct 103 ms 18932 KB Correct solution.

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7424 KB Correct solution.
2 Correct 8 ms 7424 KB Correct solution.
3 Correct 23 ms 7424 KB Correct solution.
4 Correct 9 ms 7396 KB Correct solution.
5 Correct 8 ms 7424 KB Correct solution.
6 Correct 9 ms 7552 KB Correct solution.
7 Correct 9 ms 7552 KB Correct solution.
8 Correct 11 ms 7552 KB Correct solution.
9 Correct 12 ms 7552 KB Correct solution.
10 Correct 8 ms 7552 KB Correct solution.
11 Correct 13 ms 7680 KB Correct solution.

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7424 KB Correct solution.
2 Correct 8 ms 7424 KB Correct solution.
3 Correct 23 ms 7424 KB Correct solution.
4 Correct 9 ms 7396 KB Correct solution.
5 Correct 8 ms 7424 KB Correct solution.
6 Correct 9 ms 7552 KB Correct solution.
7 Correct 9 ms 7552 KB Correct solution.
8 Correct 11 ms 7552 KB Correct solution.
9 Correct 12 ms 7552 KB Correct solution.
10 Correct 8 ms 7552 KB Correct solution.
11 Correct 13 ms 7680 KB Correct solution.
12 Correct 48 ms 11256 KB Correct solution.
13 Correct 70 ms 12536 KB Correct solution.
14 Correct 67 ms 12168 KB Correct solution.
15 Correct 72 ms 12372 KB Correct solution.
16 Correct 66 ms 12352 KB Correct solution.
17 Correct 12 ms 8064 KB Correct solution.
18 Correct 68 ms 12792 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7424 KB Correct solution.
2 Correct 7 ms 7424 KB Correct solution.
3 Correct 7 ms 7424 KB Correct solution.
4 Correct 70 ms 17404 KB Correct solution.
5 Correct 59 ms 14456 KB Correct solution.
6 Correct 91 ms 17144 KB Correct solution.
7 Correct 116 ms 19192 KB Correct solution.
8 Correct 124 ms 20940 KB Correct solution.
9 Correct 103 ms 20824 KB Correct solution.
10 Correct 8 ms 7424 KB Correct solution.
11 Correct 9 ms 7424 KB Correct solution.
12 Correct 7 ms 7424 KB Correct solution.
13 Correct 150 ms 16352 KB Correct solution.
14 Correct 7 ms 7424 KB Correct solution.
15 Correct 16 ms 8576 KB Correct solution.
16 Correct 181 ms 18584 KB Correct solution.
17 Correct 103 ms 18932 KB Correct solution.
18 Correct 7 ms 7424 KB Correct solution.
19 Correct 8 ms 7424 KB Correct solution.
20 Correct 23 ms 7424 KB Correct solution.
21 Correct 9 ms 7396 KB Correct solution.
22 Correct 8 ms 7424 KB Correct solution.
23 Correct 9 ms 7552 KB Correct solution.
24 Correct 9 ms 7552 KB Correct solution.
25 Correct 11 ms 7552 KB Correct solution.
26 Correct 12 ms 7552 KB Correct solution.
27 Correct 8 ms 7552 KB Correct solution.
28 Correct 13 ms 7680 KB Correct solution.
29 Correct 48 ms 11256 KB Correct solution.
30 Correct 70 ms 12536 KB Correct solution.
31 Correct 67 ms 12168 KB Correct solution.
32 Correct 72 ms 12372 KB Correct solution.
33 Correct 66 ms 12352 KB Correct solution.
34 Correct 12 ms 8064 KB Correct solution.
35 Correct 68 ms 12792 KB Correct solution.
36 Correct 134 ms 16604 KB Correct solution.
37 Correct 170 ms 18264 KB Correct solution.
38 Correct 189 ms 19704 KB Correct solution.
39 Correct 198 ms 19608 KB Correct solution.
40 Correct 172 ms 19600 KB Correct solution.
41 Correct 108 ms 20900 KB Correct solution.
42 Correct 185 ms 21240 KB Correct solution.