oj.uz

Submission #114370

# Submission time Handle Problem Language Result Execution time Memory
114370 2019-06-01T05:32:19 Z gs14004 Sleepy game (innopolis2018_final_D) C++17
100 / 100
 191 ms 28284 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
using lint = long long;
using pi = pair<int, int>;
 
int n, m, s;
vector<int> gph[MAXN];
vector<int> rev[MAXN];
 
int instk[MAXN], ret;
int vis2[MAXN];
 
void hascyc(int x){
	if(instk[x]) ret = 1;
	if(vis2[x]) return;
	instk[x] = 1;
	vis2[x] = 1;
	for(auto &i : rev[x]){
		hascyc(i);
	}
	instk[x] = 0;
}
 
int vis[MAXN][2], par[MAXN][2], sink[MAXN];
 
void dfs(int x, int y){
	for(auto &i : gph[x]){
		if(!vis[i][y ^ 1]){
			vis[i][y ^ 1] = 1;
			par[i][y ^ 1] = x;
			dfs(i, y ^ 1);
		}
	}
}
 
int main(){
	cin >> n >> m;
	for(int i=1; i<=n; i++){
		int w; scanf("%d",&w);
		for(int j=0; j<w; j++){
			int k;
			scanf("%d",&k);
			gph[k].push_back(i);
			rev[i].push_back(k);
		}
		if(w == 0) sink[i] = 1;
	}
	cin >> s;
	for(int i=1; i<=n; i++){
		if(sink[i] && !vis[i][0]){
			vis[i][0] = 1;
			dfs(i, 0);
		}
	}
	if(vis[s][1]){
		printf("Win\n");
		int p = 1;
		printf("%d ", s);
		while(!sink[s]){
			s = par[s][p];
			p ^= 1;
			printf("%d ", s);
		}
		return 0;
	}
	hascyc(s);
	if(ret) puts("Draw");
	else puts("Lose");
}

Compilation message

D.cpp: In function 'int main()':
D.cpp:40:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int w; scanf("%d",&w);
          ~~~~~^~~~~~~~~
D.cpp:43:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&k);
    ~~~~~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14464 KB Correct solution.
2 Correct 14 ms 14464 KB Correct solution.
3 Correct 15 ms 14464 KB Correct solution.
4 Correct 79 ms 23928 KB Correct solution.
5 Correct 65 ms 21496 KB Correct solution.
6 Correct 88 ms 24440 KB Correct solution.
7 Correct 103 ms 28284 KB Correct solution.
8 Correct 93 ms 25360 KB Correct solution.
9 Correct 99 ms 25292 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Correct solution.
2 Correct 14 ms 14436 KB Correct solution.
3 Correct 14 ms 14464 KB Correct solution.
4 Correct 139 ms 22876 KB Correct solution.
5 Correct 14 ms 14464 KB Correct solution.
6 Correct 23 ms 15616 KB Correct solution.
7 Correct 157 ms 26360 KB Correct solution.
8 Correct 97 ms 26356 KB Correct solution.

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Correct solution.
2 Correct 15 ms 14464 KB Correct solution.
3 Correct 14 ms 14464 KB Correct solution.
4 Correct 14 ms 14464 KB Correct solution.
5 Correct 12 ms 14464 KB Correct solution.
6 Correct 16 ms 14592 KB Correct solution.
7 Correct 16 ms 14592 KB Correct solution.
8 Correct 15 ms 14592 KB Correct solution.
9 Correct 15 ms 14592 KB Correct solution.
10 Correct 14 ms 14588 KB Correct solution.
11 Correct 15 ms 14592 KB Correct solution.

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Correct solution.
2 Correct 15 ms 14464 KB Correct solution.
3 Correct 14 ms 14464 KB Correct solution.
4 Correct 14 ms 14464 KB Correct solution.
5 Correct 12 ms 14464 KB Correct solution.
6 Correct 16 ms 14592 KB Correct solution.
7 Correct 16 ms 14592 KB Correct solution.
8 Correct 15 ms 14592 KB Correct solution.
9 Correct 15 ms 14592 KB Correct solution.
10 Correct 14 ms 14588 KB Correct solution.
11 Correct 15 ms 14592 KB Correct solution.
12 Correct 45 ms 17400 KB Correct solution.
13 Correct 52 ms 18300 KB Correct solution.
14 Correct 48 ms 17912 KB Correct solution.
15 Correct 50 ms 18040 KB Correct solution.
16 Correct 51 ms 18040 KB Correct solution.
17 Correct 16 ms 14976 KB Correct solution.
18 Correct 55 ms 18552 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14464 KB Correct solution.
2 Correct 14 ms 14464 KB Correct solution.
3 Correct 15 ms 14464 KB Correct solution.
4 Correct 79 ms 23928 KB Correct solution.
5 Correct 65 ms 21496 KB Correct solution.
6 Correct 88 ms 24440 KB Correct solution.
7 Correct 103 ms 28284 KB Correct solution.
8 Correct 93 ms 25360 KB Correct solution.
9 Correct 99 ms 25292 KB Correct solution.
10 Correct 13 ms 14464 KB Correct solution.
11 Correct 14 ms 14436 KB Correct solution.
12 Correct 14 ms 14464 KB Correct solution.
13 Correct 139 ms 22876 KB Correct solution.
14 Correct 14 ms 14464 KB Correct solution.
15 Correct 23 ms 15616 KB Correct solution.
16 Correct 157 ms 26360 KB Correct solution.
17 Correct 97 ms 26356 KB Correct solution.
18 Correct 13 ms 14464 KB Correct solution.
19 Correct 15 ms 14464 KB Correct solution.
20 Correct 14 ms 14464 KB Correct solution.
21 Correct 14 ms 14464 KB Correct solution.
22 Correct 12 ms 14464 KB Correct solution.
23 Correct 16 ms 14592 KB Correct solution.
24 Correct 16 ms 14592 KB Correct solution.
25 Correct 15 ms 14592 KB Correct solution.
26 Correct 15 ms 14592 KB Correct solution.
27 Correct 14 ms 14588 KB Correct solution.
28 Correct 15 ms 14592 KB Correct solution.
29 Correct 45 ms 17400 KB Correct solution.
30 Correct 52 ms 18300 KB Correct solution.
31 Correct 48 ms 17912 KB Correct solution.
32 Correct 50 ms 18040 KB Correct solution.
33 Correct 51 ms 18040 KB Correct solution.
34 Correct 16 ms 14976 KB Correct solution.
35 Correct 55 ms 18552 KB Correct solution.
36 Correct 131 ms 24536 KB Correct solution.
37 Correct 150 ms 25976 KB Correct solution.
38 Correct 162 ms 26544 KB Correct solution.
39 Correct 171 ms 23800 KB Correct solution.
40 Correct 191 ms 24596 KB Correct solution.
41 Correct 94 ms 25400 KB Correct solution.
42 Correct 163 ms 26872 KB Correct solution.