oj.uz

Submission #112993

# Submission time Handle Problem Language Result Execution time Memory
112993 2019-05-23T02:11:59 Z model_code Sleepy game (innopolis2018_final_D) C++17
100 / 100
 90 ms 16584 KB 
#include <bits/stdc++.h>
using namespace std;


void solve() {
  int n, m;
  cin >> n >> m;

  vector<vector<int>> g(n);
  for (int i = 0; i < n; ++i) {
    int c;
    cin >> c;
    for (int j = 0; j < c; ++j) {
      int v;
      cin >> v;
      --v;
      g[i].push_back(v);
    }
  }

  int start;
  cin >> start;
  --start;

  vector<vector<int>> used(2, vector<int>(n));
  vector<pair<int, int>> q = { { 0, start } };
  vector<vector<pair<int, int>>> from(2, vector<pair<int, int>>(n, { -1, -1 }));
  used[0][start] = 1;

  for (int i = 0; i < (int)q.size(); ++i) {
    int par = q[i].first;
    int v = q[i].second;
    for (int to : g[v]) {
      if (!used[!par][to]) {
        from[!par][to] = q[i];
        used[!par][to] = 1;
        q.push_back({ !par, to });
      }
    }

    if (g[v].empty() && par) {
      cout  << "Win\n";
      vector<int> vers;
      for (int x = v; x >= 0;) {
        vers.push_back(x);
        x = from[par][x].second;
        par = !par;
       }
      reverse(vers.begin(), vers.end());
      for (int x : vers) {
        cout << x + 1 << ' ';
      }
      cout << '\n';
      return;
    }
  }

  bool has_cycle = false;
  vector<int> color(n, 0);
  function<void(int)> dfs = [&](int v) {
    color[v] = 1;
    for (int to : g[v]) {
      if (color[to] == 0) {
        dfs(to);
      } else if (color[to] == 1) {
        has_cycle = true;
      }
    }
    color[v] = 2;
  };

  dfs(start);

  cout << (has_cycle ? "Draw" : "Lose") << '\n';
}


int main() {
  ios::sync_with_stdio(false);
  int tests = 1;
  // cin >> tests;
  for (int i = 0; i < tests; ++i) {
    solve();
  }
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct solution.
2 Correct 2 ms 384 KB Correct solution.
3 Correct 2 ms 384 KB Correct solution.
4 Correct 51 ms 12532 KB Correct solution.
5 Correct 24 ms 8292 KB Correct solution.
6 Correct 48 ms 11456 KB Correct solution.
7 Correct 62 ms 10528 KB Correct solution.
8 Correct 90 ms 16584 KB Correct solution.
9 Correct 76 ms 16208 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct solution.
2 Correct 2 ms 384 KB Correct solution.
3 Correct 2 ms 384 KB Correct solution.
4 Correct 41 ms 8304 KB Correct solution.
5 Correct 1 ms 384 KB Correct solution.
6 Correct 7 ms 1408 KB Correct solution.
7 Correct 69 ms 10336 KB Correct solution.
8 Correct 55 ms 11488 KB Correct solution.

Subtask #3
15.0 / 15.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct solution.
2 Correct 2 ms 384 KB Correct solution.
3 Correct 2 ms 384 KB Correct solution.
4 Correct 2 ms 384 KB Correct solution.
5 Correct 2 ms 304 KB Correct solution.
6 Correct 3 ms 512 KB Correct solution.
7 Correct 2 ms 384 KB Correct solution.
8 Correct 2 ms 384 KB Correct solution.
9 Correct 2 ms 384 KB Correct solution.
10 Correct 2 ms 512 KB Correct solution.
11 Correct 2 ms 512 KB Correct solution.
12 Correct 21 ms 2024 KB Correct solution.
13 Correct 27 ms 2296 KB Correct solution.
14 Correct 24 ms 1792 KB Correct solution.
15 Correct 23 ms 2048 KB Correct solution.
16 Correct 24 ms 1916 KB Correct solution.
17 Correct 4 ms 1152 KB Correct solution.
18 Correct 22 ms 2164 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Correct solution.
2 Correct 2 ms 384 KB Correct solution.
3 Correct 2 ms 384 KB Correct solution.
4 Correct 51 ms 12532 KB Correct solution.
5 Correct 24 ms 8292 KB Correct solution.
6 Correct 48 ms 11456 KB Correct solution.
7 Correct 62 ms 10528 KB Correct solution.
8 Correct 90 ms 16584 KB Correct solution.
9 Correct 76 ms 16208 KB Correct solution.
10 Correct 2 ms 384 KB Correct solution.
11 Correct 2 ms 384 KB Correct solution.
12 Correct 2 ms 384 KB Correct solution.
13 Correct 41 ms 8304 KB Correct solution.
14 Correct 1 ms 384 KB Correct solution.
15 Correct 7 ms 1408 KB Correct solution.
16 Correct 69 ms 10336 KB Correct solution.
17 Correct 55 ms 11488 KB Correct solution.
18 Correct 2 ms 384 KB Correct solution.
19 Correct 2 ms 384 KB Correct solution.
20 Correct 2 ms 384 KB Correct solution.
21 Correct 2 ms 384 KB Correct solution.
22 Correct 2 ms 304 KB Correct solution.
23 Correct 3 ms 512 KB Correct solution.
24 Correct 2 ms 384 KB Correct solution.
25 Correct 2 ms 384 KB Correct solution.
26 Correct 2 ms 384 KB Correct solution.
27 Correct 2 ms 512 KB Correct solution.
28 Correct 2 ms 512 KB Correct solution.
29 Correct 21 ms 2024 KB Correct solution.
30 Correct 27 ms 2296 KB Correct solution.
31 Correct 24 ms 1792 KB Correct solution.
32 Correct 23 ms 2048 KB Correct solution.
33 Correct 24 ms 1916 KB Correct solution.
34 Correct 4 ms 1152 KB Correct solution.
35 Correct 22 ms 2164 KB Correct solution.
36 Correct 35 ms 7228 KB Correct solution.
37 Correct 41 ms 8560 KB Correct solution.
38 Correct 66 ms 10336 KB Correct solution.
39 Correct 53 ms 9824 KB Correct solution.
40 Correct 84 ms 10144 KB Correct solution.
41 Correct 85 ms 16308 KB Correct solution.
42 Correct 66 ms 12360 KB Correct solution.