Submission #1111112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111112		Aza	Sleepy game (innopolis2018_final_D)	C++17	17 / 100	172 ms	262144 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()
int atleast = -1;
int n, m;
vector <int> vis;
vector <bool> skip;
vector <set<int>> g;
vector <int> pref;
int lst = -1;
bool found = false;
void dfs(int i, int cnt, int last){
	if(found)return;
	pref[i] = last;
	vis[i]++;
	if(vis[i] % 2 == 0){
		atleast = max(atleast, 0ll);
		skip[last] = true;
		return;
	}
	if(!size(g[i])){
		if(cnt % 2 == 1){
			atleast = max(atleast, 1ll);
			lst = i;
			found = true;
		}
		return;
	}
	for(auto it:g[i]){
		if(!skip[it]){
			dfs(it, cnt + 1, i);
			if(found)return;
		}
	}
}
void work(){
	cin >> n >> m;
	pref.resize(n + 1);
	vis.resize(n + 1);
	g.resize(n + 1);
	skip.resize(n + 1);
	for(int i = 1; i <= n; i++){
		int x;
		cin >> x;
		for(int j = 0; j < x; j++){
			int y;
			cin >> y;
			g[i].insert(y);
		}
	}
	int initpos;
	cin >> initpos;
	dfs(initpos, 0, -1);
	if(atleast == -1){
		cout << "Lose";
	}
	else if(atleast == 0){
		cout << "Draw";
	}
	else{
		cout << "Win\n";
		vector <int> v;
		while(lst != -1){
			v.push_back(lst);
			lst = pref[lst];
		}
		reverse(all(v));
		for(auto it:v)cout << it << " ";
	}
}
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: 0 / 19
• Subtask 3: 0 / 15
• Subtask 4: 0 / 11
• Subtask 5: 0 / 38