oj.uz

Submission #113256

# Submission time Handle Problem Language Result Execution time Memory
113256 2019-05-24T13:15:32 Z 김세빈(#2857) Sleepy game (innopolis2018_final_D) C++14
19 / 100
 146 ms 14364 KB 
#include <bits/stdc++.h>

using namespace std;

vector <int> V[202020];
queue <int> Q;
int P[202020];
bool chk[202020], fin[202020];
int n, m, s;

void dfs(int p)
{
	chk[p] = 1;
	
	for(int &t: V[p]){
		if(!chk[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);
			V[b - 1 << 1].push_back(i - 1 << 1 | 1);
			V[b - 1 << 1 | 1].push_back(i - 1 << 1);
		}
	}
	
	scanf("%d", &s);
	
	for(; !Q.empty(); ){
		p = Q.front(); Q.pop();
		for(int &t: V[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 - 1 << 1);
		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:8: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    V[b - 1 << 1].push_back(i - 1 << 1 | 1);
      ~~^~~
D.cpp:44:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    V[b - 1 << 1].push_back(i - 1 << 1 | 1);
                            ~~^~~
D.cpp:45:8: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    V[b - 1 << 1 | 1].push_back(i - 1 << 1);
      ~~^~~
D.cpp:45:34: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    V[b - 1 << 1 | 1].push_back(i - 1 << 1);
                                ~~^~~
D.cpp:61:11: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  if(chk[s - 1 << 1]){
         ~~^~~
D.cpp:63:13: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   for(i = s - 1 << 1; i != -1; i = P[i]){
           ~~^~~
D.cpp:69:9: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   dfs(s - 1 << 1);
       ~~^~~
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:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &s);
  ~~~~~^~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Correct solution.
2 Incorrect 5 ms 5120 KB Participant's answer is Lose, but jury's is Draw.
3 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Correct solution.
2 Correct 5 ms 5120 KB Correct solution.
3 Correct 6 ms 5120 KB Correct solution.
4 Correct 126 ms 12664 KB Correct solution.
5 Correct 6 ms 5120 KB Correct solution.
6 Correct 14 ms 5888 KB Correct solution.
7 Correct 146 ms 14364 KB Correct solution.
8 Correct 83 ms 14320 KB Correct solution.

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Correct solution.
2 Correct 5 ms 5120 KB Correct solution.
3 Correct 5 ms 5120 KB Correct solution.
4 Correct 5 ms 5120 KB Correct solution.
5 Correct 5 ms 5120 KB Correct solution.
6 Correct 6 ms 5120 KB Correct solution.
7 Correct 6 ms 5120 KB Correct solution.
8 Correct 7 ms 5248 KB Correct solution.
9 Correct 7 ms 5120 KB Correct solution.
10 Correct 6 ms 5120 KB Correct solution.
11 Incorrect 7 ms 5248 KB Participant's answer is Draw, but jury's is Lose.

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Correct solution.
2 Correct 5 ms 5120 KB Correct solution.
3 Correct 5 ms 5120 KB Correct solution.
4 Correct 5 ms 5120 KB Correct solution.
5 Correct 5 ms 5120 KB Correct solution.
6 Correct 6 ms 5120 KB Correct solution.
7 Correct 6 ms 5120 KB Correct solution.
8 Correct 7 ms 5248 KB Correct solution.
9 Correct 7 ms 5120 KB Correct solution.
10 Correct 6 ms 5120 KB Correct solution.
11 Incorrect 7 ms 5248 KB Participant's answer is Draw, but jury's is Lose.

Subtask #5
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Correct solution.
2 Incorrect 5 ms 5120 KB Participant's answer is Lose, but jury's is Draw.
3 Halted 0 ms 0 KB -