Submission #115480

#	Time	Username	Problem	Language	Result	Execution time	Memory
115480		youngyojun	Sleepy game (innopolis2018_final_D)	C++11	100 / 100	99 ms	21496 KiB

D

#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 / 17
• Subtask 2: 19 / 19
• Subtask 3: 15 / 15
• Subtask 4: 11 / 11
• Subtask 5: 38 / 38