oj.uz

Submission #113276

# Submission time Handle Problem Language Result Execution time Memory
113276 2019-05-24T15:06:49 Z 구사과(#2860, gs14004) Sleepy game (innopolis2018_final_D) C++14
100 / 100
 166 ms 28336 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 13 ms 14464 KB Correct solution.
2 Correct 13 ms 14464 KB Correct solution.
3 Correct 12 ms 14464 KB Correct solution.
4 Correct 72 ms 23928 KB Correct solution.
5 Correct 63 ms 21496 KB Correct solution.
6 Correct 88 ms 24444 KB Correct solution.
7 Correct 102 ms 28336 KB Correct solution.
8 Correct 130 ms 25336 KB Correct solution.
9 Correct 99 ms 25336 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14464 KB Correct solution.
2 Correct 14 ms 14464 KB Correct solution.
3 Correct 14 ms 14464 KB Correct solution.
4 Correct 156 ms 22776 KB Correct solution.
5 Correct 15 ms 14464 KB Correct solution.
6 Correct 23 ms 15616 KB Correct solution.
7 Correct 159 ms 26460 KB Correct solution.
8 Correct 96 ms 26356 KB Correct solution.

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14464 KB Correct solution.
2 Correct 14 ms 14464 KB Correct solution.
3 Correct 16 ms 14464 KB Correct solution.
4 Correct 14 ms 14464 KB Correct solution.
5 Correct 14 ms 14464 KB Correct solution.
6 Correct 14 ms 14592 KB Correct solution.
7 Correct 15 ms 14592 KB Correct solution.
8 Correct 17 ms 14592 KB Correct solution.
9 Correct 27 ms 14592 KB Correct solution.
10 Correct 20 ms 14592 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 19 ms 14464 KB Correct solution.
2 Correct 14 ms 14464 KB Correct solution.
3 Correct 16 ms 14464 KB Correct solution.
4 Correct 14 ms 14464 KB Correct solution.
5 Correct 14 ms 14464 KB Correct solution.
6 Correct 14 ms 14592 KB Correct solution.
7 Correct 15 ms 14592 KB Correct solution.
8 Correct 17 ms 14592 KB Correct solution.
9 Correct 27 ms 14592 KB Correct solution.
10 Correct 20 ms 14592 KB Correct solution.
11 Correct 15 ms 14592 KB Correct solution.
12 Correct 54 ms 17532 KB Correct solution.
13 Correct 56 ms 18296 KB Correct solution.
14 Correct 53 ms 18012 KB Correct solution.
15 Correct 50 ms 18016 KB Correct solution.
16 Correct 49 ms 18124 KB Correct solution.
17 Correct 16 ms 14976 KB Correct solution.
18 Correct 51 ms 18552 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Correct solution.
2 Correct 13 ms 14464 KB Correct solution.
3 Correct 12 ms 14464 KB Correct solution.
4 Correct 72 ms 23928 KB Correct solution.
5 Correct 63 ms 21496 KB Correct solution.
6 Correct 88 ms 24444 KB Correct solution.
7 Correct 102 ms 28336 KB Correct solution.
8 Correct 130 ms 25336 KB Correct solution.
9 Correct 99 ms 25336 KB Correct solution.
10 Correct 14 ms 14464 KB Correct solution.
11 Correct 14 ms 14464 KB Correct solution.
12 Correct 14 ms 14464 KB Correct solution.
13 Correct 156 ms 22776 KB Correct solution.
14 Correct 15 ms 14464 KB Correct solution.
15 Correct 23 ms 15616 KB Correct solution.
16 Correct 159 ms 26460 KB Correct solution.
17 Correct 96 ms 26356 KB Correct solution.
18 Correct 19 ms 14464 KB Correct solution.
19 Correct 14 ms 14464 KB Correct solution.
20 Correct 16 ms 14464 KB Correct solution.
21 Correct 14 ms 14464 KB Correct solution.
22 Correct 14 ms 14464 KB Correct solution.
23 Correct 14 ms 14592 KB Correct solution.
24 Correct 15 ms 14592 KB Correct solution.
25 Correct 17 ms 14592 KB Correct solution.
26 Correct 27 ms 14592 KB Correct solution.
27 Correct 20 ms 14592 KB Correct solution.
28 Correct 15 ms 14592 KB Correct solution.
29 Correct 54 ms 17532 KB Correct solution.
30 Correct 56 ms 18296 KB Correct solution.
31 Correct 53 ms 18012 KB Correct solution.
32 Correct 50 ms 18016 KB Correct solution.
33 Correct 49 ms 18124 KB Correct solution.
34 Correct 16 ms 14976 KB Correct solution.
35 Correct 51 ms 18552 KB Correct solution.
36 Correct 116 ms 24472 KB Correct solution.
37 Correct 136 ms 25976 KB Correct solution.
38 Correct 144 ms 26488 KB Correct solution.
39 Correct 158 ms 23800 KB Correct solution.
40 Correct 166 ms 24568 KB Correct solution.
41 Correct 97 ms 25328 KB Correct solution.
42 Correct 160 ms 27068 KB Correct solution.