oj.uz

Submission #114029

# Submission time Handle Problem Language Result Execution time Memory
114029 2019-05-29T16:13:16 Z sebinkim Sleepy game (innopolis2018_final_D) C++14
100 / 100
 190 ms 21076 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 9 ms 7552 KB Correct solution.
2 Correct 9 ms 7424 KB Correct solution.
3 Correct 12 ms 7424 KB Correct solution.
4 Correct 84 ms 17496 KB Correct solution.
5 Correct 64 ms 14432 KB Correct solution.
6 Correct 96 ms 17144 KB Correct solution.
7 Correct 106 ms 19192 KB Correct solution.
8 Correct 102 ms 20904 KB Correct solution.
9 Correct 101 ms 20788 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 8 ms 7424 KB Correct solution.
3 Correct 8 ms 7424 KB Correct solution.
4 Correct 157 ms 17660 KB Correct solution.
5 Correct 8 ms 7424 KB Correct solution.
6 Correct 17 ms 8704 KB Correct solution.
7 Correct 178 ms 19688 KB Correct solution.
8 Correct 107 ms 19956 KB Correct solution.

Subtask #3
15.0 / 15.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Correct solution.
2 Correct 8 ms 7424 KB Correct solution.
3 Correct 8 ms 7424 KB Correct solution.
4 Correct 8 ms 7424 KB Correct solution.
5 Correct 8 ms 7552 KB Correct solution.
6 Correct 9 ms 7552 KB Correct solution.
7 Correct 9 ms 7552 KB Correct solution.
8 Correct 9 ms 7552 KB Correct solution.
9 Correct 9 ms 7552 KB Correct solution.
10 Correct 9 ms 7552 KB Correct solution.
11 Correct 9 ms 7628 KB Correct solution.
12 Correct 45 ms 11316 KB Correct solution.
13 Correct 61 ms 12536 KB Correct solution.
14 Correct 53 ms 12152 KB Correct solution.
15 Correct 57 ms 12276 KB Correct solution.
16 Correct 59 ms 12280 KB Correct solution.
17 Correct 11 ms 8064 KB Correct solution.
18 Correct 53 ms 12792 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Correct solution.
2 Correct 9 ms 7424 KB Correct solution.
3 Correct 12 ms 7424 KB Correct solution.
4 Correct 84 ms 17496 KB Correct solution.
5 Correct 64 ms 14432 KB Correct solution.
6 Correct 96 ms 17144 KB Correct solution.
7 Correct 106 ms 19192 KB Correct solution.
8 Correct 102 ms 20904 KB Correct solution.
9 Correct 101 ms 20788 KB Correct solution.
10 Correct 8 ms 7424 KB Correct solution.
11 Correct 8 ms 7424 KB Correct solution.
12 Correct 8 ms 7424 KB Correct solution.
13 Correct 157 ms 17660 KB Correct solution.
14 Correct 8 ms 7424 KB Correct solution.
15 Correct 17 ms 8704 KB Correct solution.
16 Correct 178 ms 19688 KB Correct solution.
17 Correct 107 ms 19956 KB Correct solution.
18 Correct 8 ms 7424 KB Correct solution.
19 Correct 8 ms 7424 KB Correct solution.
20 Correct 8 ms 7424 KB Correct solution.
21 Correct 8 ms 7424 KB Correct solution.
22 Correct 8 ms 7552 KB Correct solution.
23 Correct 9 ms 7552 KB Correct solution.
24 Correct 9 ms 7552 KB Correct solution.
25 Correct 9 ms 7552 KB Correct solution.
26 Correct 9 ms 7552 KB Correct solution.
27 Correct 9 ms 7552 KB Correct solution.
28 Correct 9 ms 7628 KB Correct solution.
29 Correct 45 ms 11316 KB Correct solution.
30 Correct 61 ms 12536 KB Correct solution.
31 Correct 53 ms 12152 KB Correct solution.
32 Correct 57 ms 12276 KB Correct solution.
33 Correct 59 ms 12280 KB Correct solution.
34 Correct 11 ms 8064 KB Correct solution.
35 Correct 53 ms 12792 KB Correct solution.
36 Correct 128 ms 16604 KB Correct solution.
37 Correct 154 ms 18352 KB Correct solution.
38 Correct 165 ms 19704 KB Correct solution.
39 Correct 181 ms 19320 KB Correct solution.
40 Correct 154 ms 19576 KB Correct solution.
41 Correct 113 ms 20828 KB Correct solution.
42 Correct 190 ms 21076 KB Correct solution.