oj.uz

Submission #1111129

# Submission time Handle Problem Language Result Execution time Memory
1111129 2024-11-11T14:57:01 Z Aza Sleepy game (innopolis2018_final_D) C++17
100 / 100
 54 ms 25264 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 << "Win\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);
	}
	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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8272 KB Correct solution.
2 Correct 9 ms 8272 KB Correct solution.
3 Correct 6 ms 8272 KB Correct solution.
4 Correct 29 ms 18116 KB Correct solution.
5 Correct 19 ms 13768 KB Correct solution.
6 Correct 23 ms 15040 KB Correct solution.
7 Correct 36 ms 20668 KB Correct solution.
8 Correct 54 ms 25264 KB Correct solution.
9 Correct 35 ms 19904 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8284 KB Correct solution.
2 Correct 6 ms 8272 KB Correct solution.
3 Correct 6 ms 8272 KB Correct solution.
4 Correct 26 ms 11332 KB Correct solution.
5 Correct 6 ms 8272 KB Correct solution.
6 Correct 10 ms 9040 KB Correct solution.
7 Correct 40 ms 16584 KB Correct solution.
8 Correct 46 ms 16388 KB Correct solution.

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8284 KB Correct solution.
2 Correct 6 ms 8272 KB Correct solution.
3 Correct 5 ms 8108 KB Correct solution.
4 Correct 6 ms 8440 KB Correct solution.
5 Correct 6 ms 8272 KB Correct solution.
6 Correct 6 ms 8272 KB Correct solution.
7 Correct 6 ms 8272 KB Correct solution.
8 Correct 7 ms 8272 KB Correct solution.
9 Correct 7 ms 8272 KB Correct solution.
10 Correct 6 ms 8272 KB Correct solution.
11 Correct 7 ms 8272 KB Correct solution.

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8284 KB Correct solution.
2 Correct 6 ms 8272 KB Correct solution.
3 Correct 5 ms 8108 KB Correct solution.
4 Correct 6 ms 8440 KB Correct solution.
5 Correct 6 ms 8272 KB Correct solution.
6 Correct 6 ms 8272 KB Correct solution.
7 Correct 6 ms 8272 KB Correct solution.
8 Correct 7 ms 8272 KB Correct solution.
9 Correct 7 ms 8272 KB Correct solution.
10 Correct 6 ms 8272 KB Correct solution.
11 Correct 7 ms 8272 KB Correct solution.
12 Correct 20 ms 10836 KB Correct solution.
13 Correct 22 ms 11600 KB Correct solution.
14 Correct 19 ms 10576 KB Correct solution.
15 Correct 16 ms 10576 KB Correct solution.
16 Correct 20 ms 10576 KB Correct solution.
17 Correct 7 ms 8784 KB Correct solution.
18 Correct 19 ms 11088 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8272 KB Correct solution.
2 Correct 9 ms 8272 KB Correct solution.
3 Correct 6 ms 8272 KB Correct solution.
4 Correct 29 ms 18116 KB Correct solution.
5 Correct 19 ms 13768 KB Correct solution.
6 Correct 23 ms 15040 KB Correct solution.
7 Correct 36 ms 20668 KB Correct solution.
8 Correct 54 ms 25264 KB Correct solution.
9 Correct 35 ms 19904 KB Correct solution.
10 Correct 6 ms 8284 KB Correct solution.
11 Correct 6 ms 8272 KB Correct solution.
12 Correct 6 ms 8272 KB Correct solution.
13 Correct 26 ms 11332 KB Correct solution.
14 Correct 6 ms 8272 KB Correct solution.
15 Correct 10 ms 9040 KB Correct solution.
16 Correct 40 ms 16584 KB Correct solution.
17 Correct 46 ms 16388 KB Correct solution.
18 Correct 6 ms 8284 KB Correct solution.
19 Correct 6 ms 8272 KB Correct solution.
20 Correct 5 ms 8108 KB Correct solution.
21 Correct 6 ms 8440 KB Correct solution.
22 Correct 6 ms 8272 KB Correct solution.
23 Correct 6 ms 8272 KB Correct solution.
24 Correct 6 ms 8272 KB Correct solution.
25 Correct 7 ms 8272 KB Correct solution.
26 Correct 7 ms 8272 KB Correct solution.
27 Correct 6 ms 8272 KB Correct solution.
28 Correct 7 ms 8272 KB Correct solution.
29 Correct 20 ms 10836 KB Correct solution.
30 Correct 22 ms 11600 KB Correct solution.
31 Correct 19 ms 10576 KB Correct solution.
32 Correct 16 ms 10576 KB Correct solution.
33 Correct 20 ms 10576 KB Correct solution.
34 Correct 7 ms 8784 KB Correct solution.
35 Correct 19 ms 11088 KB Correct solution.
36 Correct 24 ms 11088 KB Correct solution.
37 Correct 27 ms 11600 KB Correct solution.
38 Correct 43 ms 16592 KB Correct solution.
39 Correct 27 ms 11856 KB Correct solution.
40 Correct 37 ms 12008 KB Correct solution.
41 Correct 36 ms 20156 KB Correct solution.
42 Correct 35 ms 16320 KB Correct solution.