oj.uz

Submission #115480

# Submission time Handle Problem Language Result Execution time Memory
115480 2019-06-07T16:01:02 Z youngyojun Sleepy game (innopolis2018_final_D) C++11
100 / 100
 99 ms 21496 KB 
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;

const int MAXN = 100055;

vector<int> G[MAXN];

int A[MAXN*2];
bitset<MAXN*2> chk, isd;

int N, M;

void f(int i) {
	chk[i] = true;
	if(G[i>>1].empty() && (i&1)) {
		vector<int> V;
		for(int v = i; v;) {
			V.eb(v);
			v = A[v];
		}
		reverse(V.begin(), V.end());
		puts("Win");
		for(int v : V) printf("%d ", v >> 1);
		puts("");
		exit(0);
	}
	i ^= 1;
	for(int v : G[i>>1]) {
		v <<= 1; v |= i & 1;
		if(chk[v]) continue;
		A[v] = i ^ 1;
		f(v);
	}
}

void g(int i) {
	chk[i] = true;
	for(int v : G[i]) {
		if(chk[v]) {
			if(isd[v]) continue;
			puts("Draw");
			exit(0);
		}
		g(v);
	}
	isd[i] = true;
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for(int i = 1; i <= N; i++) {
		cin >> M;
		for(int v; M--;) {
			cin >> v;
			G[i].eb(v);
		}
	}

	cin >> M;
	f(M << 1);
	chk.reset();
	g(M);
	
	puts("Lose");
	return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Correct solution.
2 Correct 4 ms 2688 KB Correct solution.
3 Correct 4 ms 2816 KB Correct solution.
4 Correct 67 ms 14584 KB Correct solution.
5 Correct 33 ms 9464 KB Correct solution.
6 Correct 53 ms 11128 KB Correct solution.
7 Correct 83 ms 17904 KB Correct solution.
8 Correct 99 ms 21496 KB Correct solution.
9 Correct 86 ms 16792 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Correct solution.
2 Correct 4 ms 2688 KB Correct solution.
3 Correct 0 ms 2688 KB Correct solution.
4 Correct 43 ms 6780 KB Correct solution.
5 Correct 5 ms 2688 KB Correct solution.
6 Correct 13 ms 3712 KB Correct solution.
7 Correct 82 ms 13304 KB Correct solution.
8 Correct 76 ms 13176 KB Correct solution.

Subtask #3
15.0 / 15.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Correct solution.
2 Correct 5 ms 2816 KB Correct solution.
3 Correct 4 ms 2688 KB Correct solution.
4 Correct 4 ms 2688 KB Correct solution.
5 Correct 3 ms 2688 KB Correct solution.
6 Correct 5 ms 2816 KB Correct solution.
7 Correct 4 ms 2816 KB Correct solution.
8 Correct 5 ms 2816 KB Correct solution.
9 Correct 5 ms 2816 KB Correct solution.
10 Correct 4 ms 2816 KB Correct solution.
11 Correct 5 ms 2816 KB Correct solution.
12 Correct 26 ms 5244 KB Correct solution.
13 Correct 29 ms 5860 KB Correct solution.
14 Correct 26 ms 4992 KB Correct solution.
15 Correct 24 ms 4992 KB Correct solution.
16 Correct 25 ms 4856 KB Correct solution.
17 Correct 6 ms 3456 KB Correct solution.
18 Correct 25 ms 5240 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Correct solution.
2 Correct 4 ms 2688 KB Correct solution.
3 Correct 4 ms 2816 KB Correct solution.
4 Correct 67 ms 14584 KB Correct solution.
5 Correct 33 ms 9464 KB Correct solution.
6 Correct 53 ms 11128 KB Correct solution.
7 Correct 83 ms 17904 KB Correct solution.
8 Correct 99 ms 21496 KB Correct solution.
9 Correct 86 ms 16792 KB Correct solution.
10 Correct 4 ms 2688 KB Correct solution.
11 Correct 4 ms 2688 KB Correct solution.
12 Correct 0 ms 2688 KB Correct solution.
13 Correct 43 ms 6780 KB Correct solution.
14 Correct 5 ms 2688 KB Correct solution.
15 Correct 13 ms 3712 KB Correct solution.
16 Correct 82 ms 13304 KB Correct solution.
17 Correct 76 ms 13176 KB Correct solution.
18 Correct 4 ms 2688 KB Correct solution.
19 Correct 5 ms 2816 KB Correct solution.
20 Correct 4 ms 2688 KB Correct solution.
21 Correct 4 ms 2688 KB Correct solution.
22 Correct 3 ms 2688 KB Correct solution.
23 Correct 5 ms 2816 KB Correct solution.
24 Correct 4 ms 2816 KB Correct solution.
25 Correct 5 ms 2816 KB Correct solution.
26 Correct 5 ms 2816 KB Correct solution.
27 Correct 4 ms 2816 KB Correct solution.
28 Correct 5 ms 2816 KB Correct solution.
29 Correct 26 ms 5244 KB Correct solution.
30 Correct 29 ms 5860 KB Correct solution.
31 Correct 26 ms 4992 KB Correct solution.
32 Correct 24 ms 4992 KB Correct solution.
33 Correct 25 ms 4856 KB Correct solution.
34 Correct 6 ms 3456 KB Correct solution.
35 Correct 25 ms 5240 KB Correct solution.
36 Correct 35 ms 6264 KB Correct solution.
37 Correct 39 ms 6912 KB Correct solution.
38 Correct 76 ms 13304 KB Correct solution.
39 Correct 41 ms 8056 KB Correct solution.
40 Correct 66 ms 8056 KB Correct solution.
41 Correct 85 ms 16888 KB Correct solution.
42 Correct 73 ms 12796 KB Correct solution.