oj.uz

Submission #1111128

# Submission time Handle Problem Language Result Execution time Memory
1111128 2024-11-11T14:56:18 Z Aza Sleepy game (innopolis2018_final_D) C++17
100 / 100
 59 ms 25936 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);
	}
	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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8272 KB Correct solution.
2 Correct 6 ms 8272 KB Correct solution.
3 Correct 6 ms 8100 KB Correct solution.
4 Correct 32 ms 18216 KB Correct solution.
5 Correct 21 ms 13768 KB Correct solution.
6 Correct 28 ms 15060 KB Correct solution.
7 Correct 45 ms 20668 KB Correct solution.
8 Correct 54 ms 25936 KB Correct solution.
9 Correct 39 ms 20720 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8272 KB Correct solution.
2 Correct 6 ms 8272 KB Correct solution.
3 Correct 7 ms 8216 KB Correct solution.
4 Correct 30 ms 12396 KB Correct solution.
5 Correct 9 ms 8284 KB Correct solution.
6 Correct 10 ms 9040 KB Correct solution.
7 Correct 48 ms 17616 KB Correct solution.
8 Correct 45 ms 17176 KB Correct solution.

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8272 KB Correct solution.
2 Correct 7 ms 8272 KB Correct solution.
3 Correct 9 ms 8284 KB Correct solution.
4 Correct 7 ms 8284 KB Correct solution.
5 Correct 9 ms 8528 KB Correct solution.
6 Correct 7 ms 8272 KB Correct solution.
7 Correct 7 ms 8248 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 8272 KB Correct solution.
2 Correct 7 ms 8272 KB Correct solution.
3 Correct 9 ms 8284 KB Correct solution.
4 Correct 7 ms 8284 KB Correct solution.
5 Correct 9 ms 8528 KB Correct solution.
6 Correct 7 ms 8272 KB Correct solution.
7 Correct 7 ms 8248 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 29 ms 11584 KB Correct solution.
13 Correct 24 ms 12588 KB Correct solution.
14 Correct 20 ms 11600 KB Correct solution.
15 Correct 27 ms 11600 KB Correct solution.
16 Correct 21 ms 11496 KB Correct solution.
17 Correct 10 ms 8784 KB Correct solution.
18 Correct 21 ms 11860 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 6 ms 8272 KB Correct solution.
3 Correct 6 ms 8100 KB Correct solution.
4 Correct 32 ms 18216 KB Correct solution.
5 Correct 21 ms 13768 KB Correct solution.
6 Correct 28 ms 15060 KB Correct solution.
7 Correct 45 ms 20668 KB Correct solution.
8 Correct 54 ms 25936 KB Correct solution.
9 Correct 39 ms 20720 KB Correct solution.
10 Correct 6 ms 8272 KB Correct solution.
11 Correct 6 ms 8272 KB Correct solution.
12 Correct 7 ms 8216 KB Correct solution.
13 Correct 30 ms 12396 KB Correct solution.
14 Correct 9 ms 8284 KB Correct solution.
15 Correct 10 ms 9040 KB Correct solution.
16 Correct 48 ms 17616 KB Correct solution.
17 Correct 45 ms 17176 KB Correct solution.
18 Correct 6 ms 8272 KB Correct solution.
19 Correct 7 ms 8272 KB Correct solution.
20 Correct 9 ms 8284 KB Correct solution.
21 Correct 7 ms 8284 KB Correct solution.
22 Correct 9 ms 8528 KB Correct solution.
23 Correct 7 ms 8272 KB Correct solution.
24 Correct 7 ms 8248 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 29 ms 11584 KB Correct solution.
30 Correct 24 ms 12588 KB Correct solution.
31 Correct 20 ms 11600 KB Correct solution.
32 Correct 27 ms 11600 KB Correct solution.
33 Correct 21 ms 11496 KB Correct solution.
34 Correct 10 ms 8784 KB Correct solution.
35 Correct 21 ms 11860 KB Correct solution.
36 Correct 30 ms 12112 KB Correct solution.
37 Correct 29 ms 12880 KB Correct solution.
38 Correct 49 ms 17844 KB Correct solution.
39 Correct 30 ms 13164 KB Correct solution.
40 Correct 59 ms 13384 KB Correct solution.
41 Correct 56 ms 20708 KB Correct solution.
42 Correct 41 ms 17856 KB Correct solution.