oj.uz

Submission #330774

# Submission time Handle Problem Language Result Execution time Memory
330774 2020-11-26T14:25:39 Z Valera_Grinenko Sleepy game (innopolis2018_final_D) C++17
100 / 100
 74 ms 19808 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cmath>
#include <queue>
#include <bitset>
#include <numeric>
#include <array>
#include <cstring>
#include <random>
#include <chrono>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 1e5 + 42;
vector<int> g[N];
int dp[N][2] = {0};
int n, m;
int s;
bool draw = false;
vector<int> ans;
void dfs(int v, int move) {
  dp[v][move] = 1;
  ans.pb(v);
  if(!g[v].size() && move) {
    cout << "Win\n";
    for(auto& x : ans) cout << x << ' ';
    exit(0);
  }
  for(auto& x : g[v]) {
    if(dp[x][(move ^ 1)] == 1) draw = true;
    if(!dp[x][(move ^ 1)]) dfs(x, (move ^ 1));
  }
  dp[v][move] = 2;
  ans.pop_back();
}
int main() {

  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  cin >> n >> m;

  for(int i = 1; i <= n; i++) {
    int c; cin >> c;
    for(int j = 0; j < c; j++) {
      int to; cin >> to;
      g[i].pb(to);
    }
  }

  cin >> s;

  dfs(s, 0);

  cout << (draw ? "Draw\n" : "Lose\n");

  return 0;
}
/*
5 5
1 2
1 3
2 1 4
1 5
0
1
*/

Compilation message

D.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Correct solution.
2 Correct 2 ms 2668 KB Correct solution.
3 Correct 2 ms 2668 KB Correct solution.
4 Correct 43 ms 13672 KB Correct solution.
5 Correct 22 ms 8940 KB Correct solution.
6 Correct 35 ms 10728 KB Correct solution.
7 Correct 58 ms 16356 KB Correct solution.
8 Correct 74 ms 19808 KB Correct solution.
9 Correct 50 ms 15716 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Correct solution.
2 Correct 2 ms 2668 KB Correct solution.
3 Correct 2 ms 2668 KB Correct solution.
4 Correct 39 ms 6636 KB Correct solution.
5 Correct 2 ms 2668 KB Correct solution.
6 Correct 8 ms 3692 KB Correct solution.
7 Correct 70 ms 12528 KB Correct solution.
8 Correct 57 ms 12400 KB Correct solution.

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Correct solution.
2 Correct 2 ms 2668 KB Correct solution.
3 Correct 2 ms 2668 KB Correct solution.
4 Correct 3 ms 2668 KB Correct solution.
5 Correct 2 ms 2668 KB Correct solution.
6 Correct 3 ms 2796 KB Correct solution.
7 Correct 4 ms 2796 KB Correct solution.
8 Correct 3 ms 2796 KB Correct solution.
9 Correct 3 ms 2796 KB Correct solution.
10 Correct 3 ms 2796 KB Correct solution.
11 Correct 3 ms 2796 KB Correct solution.

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Correct solution.
2 Correct 2 ms 2668 KB Correct solution.
3 Correct 2 ms 2668 KB Correct solution.
4 Correct 3 ms 2668 KB Correct solution.
5 Correct 2 ms 2668 KB Correct solution.
6 Correct 3 ms 2796 KB Correct solution.
7 Correct 4 ms 2796 KB Correct solution.
8 Correct 3 ms 2796 KB Correct solution.
9 Correct 3 ms 2796 KB Correct solution.
10 Correct 3 ms 2796 KB Correct solution.
11 Correct 3 ms 2796 KB Correct solution.
12 Correct 29 ms 5228 KB Correct solution.
13 Correct 26 ms 5832 KB Correct solution.
14 Correct 24 ms 5100 KB Correct solution.
15 Correct 23 ms 4972 KB Correct solution.
16 Correct 23 ms 4972 KB Correct solution.
17 Correct 6 ms 3308 KB Correct solution.
18 Correct 23 ms 5228 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Correct solution.
2 Correct 2 ms 2668 KB Correct solution.
3 Correct 2 ms 2668 KB Correct solution.
4 Correct 43 ms 13672 KB Correct solution.
5 Correct 22 ms 8940 KB Correct solution.
6 Correct 35 ms 10728 KB Correct solution.
7 Correct 58 ms 16356 KB Correct solution.
8 Correct 74 ms 19808 KB Correct solution.
9 Correct 50 ms 15716 KB Correct solution.
10 Correct 2 ms 2668 KB Correct solution.
11 Correct 2 ms 2668 KB Correct solution.
12 Correct 2 ms 2668 KB Correct solution.
13 Correct 39 ms 6636 KB Correct solution.
14 Correct 2 ms 2668 KB Correct solution.
15 Correct 8 ms 3692 KB Correct solution.
16 Correct 70 ms 12528 KB Correct solution.
17 Correct 57 ms 12400 KB Correct solution.
18 Correct 2 ms 2668 KB Correct solution.
19 Correct 2 ms 2668 KB Correct solution.
20 Correct 2 ms 2668 KB Correct solution.
21 Correct 3 ms 2668 KB Correct solution.
22 Correct 2 ms 2668 KB Correct solution.
23 Correct 3 ms 2796 KB Correct solution.
24 Correct 4 ms 2796 KB Correct solution.
25 Correct 3 ms 2796 KB Correct solution.
26 Correct 3 ms 2796 KB Correct solution.
27 Correct 3 ms 2796 KB Correct solution.
28 Correct 3 ms 2796 KB Correct solution.
29 Correct 29 ms 5228 KB Correct solution.
30 Correct 26 ms 5832 KB Correct solution.
31 Correct 24 ms 5100 KB Correct solution.
32 Correct 23 ms 4972 KB Correct solution.
33 Correct 23 ms 4972 KB Correct solution.
34 Correct 6 ms 3308 KB Correct solution.
35 Correct 23 ms 5228 KB Correct solution.
36 Correct 43 ms 6252 KB Correct solution.
37 Correct 40 ms 6892 KB Correct solution.
38 Correct 72 ms 12784 KB Correct solution.
39 Correct 40 ms 8044 KB Correct solution.
40 Correct 60 ms 8320 KB Correct solution.
41 Correct 50 ms 15716 KB Correct solution.
42 Correct 52 ms 12264 KB Correct solution.