oj.uz

Submission #1111112

# Submission time Handle Problem Language Result Execution time Memory
1111112 2024-11-11T13:59:03 Z Aza Sleepy game (innopolis2018_final_D) C++17
17 / 100
 172 ms 262144 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;
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.0 / 17.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 39 ms 13640 KB Correct solution.
5 Correct 14 ms 9040 KB Correct solution.
6 Correct 21 ms 13392 KB Correct solution.
7 Correct 47 ms 19132 KB Correct solution.
8 Correct 28 ms 18128 KB Correct solution.
9 Correct 29 ms 17656 KB Correct solution.

Subtask #2
0 / 19.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 31 ms 17488 KB Correct solution.
5 Correct 1 ms 336 KB Correct solution.
6 Correct 6 ms 2384 KB Correct solution.
7 Correct 46 ms 21192 KB Correct solution.
8 Incorrect 40 ms 17736 KB Participant's answer is Draw, but jury's is Win.
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 172 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 172 ms 262144 KB Execution killed with signal 9
2 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 336 KB Correct solution.
3 Correct 1 ms 336 KB Correct solution.
4 Correct 39 ms 13640 KB Correct solution.
5 Correct 14 ms 9040 KB Correct solution.
6 Correct 21 ms 13392 KB Correct solution.
7 Correct 47 ms 19132 KB Correct solution.
8 Correct 28 ms 18128 KB Correct solution.
9 Correct 29 ms 17656 KB Correct solution.
10 Correct 1 ms 336 KB Correct solution.
11 Correct 1 ms 336 KB Correct solution.
12 Correct 1 ms 336 KB Correct solution.
13 Correct 31 ms 17488 KB Correct solution.
14 Correct 1 ms 336 KB Correct solution.
15 Correct 6 ms 2384 KB Correct solution.
16 Correct 46 ms 21192 KB Correct solution.
17 Incorrect 40 ms 17736 KB Participant's answer is Draw, but jury's is Win.
18 Halted 0 ms 0 KB -