oj.uz

Submission #1111127

# Submission time Handle Problem Language Result Execution time Memory
1111127 2024-11-11T14:55:49 Z Aza Sleepy game (innopolis2018_final_D) C++17
0 / 100
 37 ms 21148 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()
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 << "Won\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);
	}
	dp[cur][move] = 2;
	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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8272 KB Correct solution.
2 Correct 8 ms 8096 KB Correct solution.
3 Correct 6 ms 8272 KB Correct solution.
4 Correct 30 ms 18636 KB Correct solution.
5 Correct 19 ms 14280 KB Correct solution.
6 Correct 24 ms 15560 KB Correct solution.
7 Incorrect 37 ms 21148 KB Token "Won" doesn't correspond to pattern "Win|Lose|Draw"
8 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8272 KB Correct solution.
2 Incorrect 6 ms 8272 KB Token "Won" doesn't correspond to pattern "Win|Lose|Draw"
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 8056 KB Token "Won" doesn't correspond to pattern "Win|Lose|Draw"
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 8056 KB Token "Won" doesn't correspond to pattern "Win|Lose|Draw"
2 Halted 0 ms 0 KB -

Subtask #5
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8272 KB Correct solution.
2 Correct 8 ms 8096 KB Correct solution.
3 Correct 6 ms 8272 KB Correct solution.
4 Correct 30 ms 18636 KB Correct solution.
5 Correct 19 ms 14280 KB Correct solution.
6 Correct 24 ms 15560 KB Correct solution.
7 Incorrect 37 ms 21148 KB Token "Won" doesn't correspond to pattern "Win|Lose|Draw"
8 Halted 0 ms 0 KB -