Submission #1111129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111129		Aza	Sleepy game (innopolis2018_final_D)	C++17	100 / 100	54 ms	25264 KiB

D

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#define size(x) (int)x.size()
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin (),x.rend()
bool did = false;
const int N = 1e5 + 6;
vector <vector<int>> g(N);
vector <vector <int>> dp(N, vector <int>(2));
vector <int> ans;
bool draw = false;
void dfs(int cur, int move){
	dp[cur][move] = 1;
	ans.push_back(cur);
	if(g[cur].empty() and move){
		cout << "Win\n";
		for(auto it:ans){
			cout << it << " ";
		}
		did = true;
		exit(0);
	}
	for(auto it:g[cur]){
		if(dp[it][move ^ 1] == 1)draw = true;
		if(!dp[it][move ^ 1])dfs(it, move ^ 1);
	}
	ans.pop_back();
}
void work(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		int x;
		cin >> x;
		for(int j = 0; j < x; j++){
			int y;
			cin >> y;
			g[i].push_back(y);
		}
	}
	int initpos;
	cin >> initpos;
	dfs(initpos, 0);
	cout << (draw ? "Draw":"Lose");
}
signed main(){
   	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   	int tasks = 1;
	//cin >> tasks;
   	while(tasks--){
   		work();
   		cout << endl;
   	}
}
/*
5 6
2 2 3
2 4 5
1 4
1 5
0
1
*/

• Subtask 1: 17 / 17
• Subtask 2: 19 / 19
• Subtask 3: 15 / 15
• Subtask 4: 11 / 11
• Subtask 5: 38 / 38