oj.uz

Submission #1111100

# Submission time Handle Problem Language Result Execution time Memory
1111100 2024-11-11T13:44:29 Z Aza Sleepy game (innopolis2018_final_D) C++17
17 / 100
 51 ms 21440 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -