oj.uz

Submission #113250

# Submission time Handle Problem Language Result Execution time Memory
113250 2019-05-24T12:16:55 Z 김세빈(#2857) Sleepy game (innopolis2018_final_D) C++14
0 / 100
 2000 ms 11256 KB 
#include <bits/stdc++.h>

using namespace std;

vector <int> V[101010], V2[101010], Q;
int D[101010], P[101010];
bool chk[101010], ans[101010], dis[101010];
bool chk2[101010], ans2[101010];
int n, m, s;

void check(int p, int v, int r)
{
	chk[p] = 1; ans[p] = v;
	P[p] = r;
	
	if(v == 0){
		for(int &t: V[p]){
			 if(!chk[t]){
			 	check(t, 1, p);
			 }
		}
	}
	else{
		for(int &t: V[p]){	
			if(!chk[t]){
				D[t] --;
				if(D[t] == 0) check(t, 0, p);
			}
		}
	}
}

int main()
{
	int i, a, b, p;
	bool f = 0;
	
	scanf("%d%d", &n, &m);
	
	for(i=1; i<=n; i++){
		scanf("%d", &a); D[i] = a;
		
		for(; a--; ){
			scanf("%d", &b);
			V[b].push_back(i);
			V2[i].push_back(b);
		}
		
		if(D[i] == 0) check(i, 0, 0);
	}
	
	for(int t=1; t<=n; t++){
	for(i=1; i<=n; i++){
		if(chk2[i]) continue;
		bool f2 = 0;
		for(int j=0; j<V2[i].size(); j++){
			if(chk2[V2[i][j]] && !ans2[V2[i][j]]){
				chk2[i] = 1; ans2[i] = 1;
				break;
			}
			else if(!chk2[V2[i][j]]) f2 = 1;
		}
		if(!chk2[i] && !f2){
			chk2[i] = 1; ans2[i] = 0;
		}
	}
	}
	
	for(i=1; i<=n; i++){
		chk[i] = chk2[i]; ans[i] = ans2[i];
//		if(chk[i] != chk2[i] || ans[i] != ans2[i]) return 1 / 0;
	}
	
	scanf("%d", &s);
	
	if(ans[s]){
		printf("Win\n");
		for(; s; s=P[s]) printf("%d ", s);
		printf("\n");
		return 0;
	}
	
	for(i=1; i<=n; i++){
		for(int &t: V[i]) if(t == s) {
			dis[i] = 1;
			break;
		}
	}
	
	for(i=1; i<=n; i++){
		for(int &t: V[i]) if(dis[t]){
			if(ans[i]){
				printf("Win\n%d %d", s, t);
				for(s=i; s; s=P[s]) printf(" %d", s);
				printf("\n");
				return 0;
			}
			else if(!chk[i]) f = 1;
			break;
		}
	}
	
	if(f) printf("Draw\n");
	else printf("Lose\n");
	
	return 0;
}

Compilation message

D.cpp: In function 'int main()':
D.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<V2[i].size(); j++){
                ~^~~~~~~~~~~~~
D.cpp:35:15: warning: unused variable 'p' [-Wunused-variable]
  int i, a, b, p;
               ^
D.cpp:38: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:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a); D[i] = a;
   ~~~~~^~~~~~~~~~
D.cpp:44:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &b);
    ~~~~~^~~~~~~~~~
D.cpp:74: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 Correct 5 ms 5120 KB Correct solution.
3 Correct 6 ms 5248 KB Correct solution.
4 Execution timed out 2058 ms 11256 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 5 ms 5120 KB There are some edges from last vertex 72. The game didn't end.
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5116 KB Correct solution.
2 Correct 5 ms 5120 KB Correct solution.
3 Correct 5 ms 5120 KB Correct solution.
4 Correct 6 ms 5120 KB Correct solution.
5 Correct 6 ms 5120 KB Correct solution.
6 Incorrect 11 ms 5120 KB There are some edges from last vertex 66. The game didn't end.
7 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5116 KB Correct solution.
2 Correct 5 ms 5120 KB Correct solution.
3 Correct 5 ms 5120 KB Correct solution.
4 Correct 6 ms 5120 KB Correct solution.
5 Correct 6 ms 5120 KB Correct solution.
6 Incorrect 11 ms 5120 KB There are some edges from last vertex 66. The game didn't end.
7 Halted 0 ms 0 KB -

Subtask #5
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Correct solution.
2 Correct 5 ms 5120 KB Correct solution.
3 Correct 6 ms 5248 KB Correct solution.
4 Execution timed out 2058 ms 11256 KB Time limit exceeded
5 Halted 0 ms 0 KB -