Submission #112993

#	Time	Username	Problem	Language	Result	Execution time	Memory
112993		model_code	Sleepy game (innopolis2018_final_D)	C++17	100 / 100	90 ms	16584 KiB

D

#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 / 17
• Subtask 2: 19 / 19
• Subtask 3: 15 / 15
• Subtask 4: 11 / 11
• Subtask 5: 38 / 38