답안 #1111100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111100	2024-11-11T13:44:29 Z	Aza	Sleepy game (innopolis2018_final_D)	C++17	17 / 100	51 ms	21440 KB

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;
stack<int> st;
bool found = false;
void dfs(int i, int cnt, int last){
	if(found)return;
	vis[i]++;
	st.push(i);
	if(vis[i] % 2 == 0){
		atleast = max(atleast, 0ll);
		st.pop();
		skip[last] = true;
		return;
	}
	if(!size(g[i])){
		if(cnt % 2 == 1){
			atleast = max(atleast, 1ll);
			found = true;
		}
		return;
	}
	for(auto it:g[i]){
		if(!skip[it]){
			dfs(it, cnt + 1, i);
			if(found)return;
		}
	}
}
void work(){
	cin >> n >> m;
	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(!st.empty()){
			v.push_back(st.top());
			st.pop();
		}
		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;
   	}
}

Subtask #1

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Correct solution.
2	Correct	1 ms	504 KB	Correct solution.
3	Correct	1 ms	336 KB	Correct solution.
4	Correct	22 ms	14812 KB	Correct solution.
5	Correct	16 ms	10064 KB	Correct solution.
6	Correct	28 ms	14412 KB	Correct solution.
7	Correct	51 ms	21440 KB	Correct solution.
8	Correct	31 ms	20048 KB	Correct solution.
9	Correct	31 ms	20048 KB	Correct solution.

Subtask #2

0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Correct solution.
2	Incorrect	1 ms	336 KB	There is no edge between vertices 20 and 63.
3	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Correct solution.
2	Correct	1 ms	336 KB	Correct solution.
3	Correct	1 ms	336 KB	Correct solution.
4	Correct	1 ms	336 KB	Correct solution.
5	Incorrect	1 ms	336 KB	There is no edge between vertices 16 and 26.
6	Halted	0 ms	0 KB	-

Subtask #4

0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Correct solution.
2	Correct	1 ms	336 KB	Correct solution.
3	Correct	1 ms	336 KB	Correct solution.
4	Correct	1 ms	336 KB	Correct solution.
5	Incorrect	1 ms	336 KB	There is no edge between vertices 16 and 26.
6	Halted	0 ms	0 KB	-

Subtask #5

0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Correct solution.
2	Correct	1 ms	504 KB	Correct solution.
3	Correct	1 ms	336 KB	Correct solution.
4	Correct	22 ms	14812 KB	Correct solution.
5	Correct	16 ms	10064 KB	Correct solution.
6	Correct	28 ms	14412 KB	Correct solution.
7	Correct	51 ms	21440 KB	Correct solution.
8	Correct	31 ms	20048 KB	Correct solution.
9	Correct	31 ms	20048 KB	Correct solution.
10	Correct	1 ms	336 KB	Correct solution.
11	Incorrect	1 ms	336 KB	There is no edge between vertices 20 and 63.
12	Halted	0 ms	0 KB	-