oj.uz

Submission #390841

# Submission time Handle Problem Language Result Execution time Memory
390841 2021-04-17T07:23:36 Z acm Sleepy game (innopolis2018_final_D) C++14
100 / 100
 67 ms 19396 KB 
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define precision     \
  cout.precision(30); \
  cerr.precision(10);
#define ll long long
#define ld long double
#define pll pair<ll, ll>
#define pii pair<int, int>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) for (int i = l; i != r; (l > r ? i-- : i++))
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define mp(x, y) make_pair(x, y)
#define all(x) x.begin(), x.end()
#define pc(x) __builtin_popcount(x)
#define pcll(x) __builtin_popcountll(x)
#define F first
#define S second
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void ioi(string name) {
  freopen((name + ".in").c_str(), "r", stdin);
  freopen((name + ".out").c_str(), "w", stdout);
}
int n, m, c, r, t[200005], w[200005][2];
vector<int> g[200005];
void dfs(int v = r, int k = 0, int p = -1) {
  w[v][k] = p;
  for (auto to : g[v]) {
    if (!w[to][!k]) dfs(to, !k, v);
  }
}
void sfd(int v = r) {
  t[v] = 1;
  for (auto to : g[v]) {
    if (!t[to])
      sfd(to);
    else if (t[to] == 1)
      c = 1;
  }
  t[v] = 2;
}
int main() {
  speed;
  precision;
  // code
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    while (x--) {
      int v;
      cin >> v;
      g[i].pb(v);
    }
  }
  cin >> r;
  dfs();
  for (int i = 1; i <= n; i++) {
    if (!sz(g[i]) && w[i][1]) {
      cout << "Win\n";
      vector<int> e;
      int v = i, k = 1;
      e.pb(v);
      while (w[v][k] > 0) {
        e.pb(w[v][k]);
        v = w[v][k];
        k ^= 1;
      }
      reverse(all(e));
      for (auto u : e) cout << u << " ";
      return 0;
    }
  }
  sfd();
  cout << (c ? "Draw" : "Lose");
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Compilation message

D.cpp: In function 'void ioi(std::string)':
D.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   26 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
D.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   27 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4980 KB Correct solution.
2 Correct 4 ms 4940 KB Correct solution.
3 Correct 3 ms 4940 KB Correct solution.
4 Correct 41 ms 14528 KB Correct solution.
5 Correct 24 ms 10496 KB Correct solution.
6 Correct 36 ms 12228 KB Correct solution.
7 Correct 57 ms 16988 KB Correct solution.
8 Correct 62 ms 19396 KB Correct solution.
9 Correct 56 ms 16324 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Correct solution.
2 Correct 4 ms 4952 KB Correct solution.
3 Correct 4 ms 4940 KB Correct solution.
4 Correct 41 ms 9000 KB Correct solution.
5 Correct 3 ms 5028 KB Correct solution.
6 Correct 9 ms 5836 KB Correct solution.
7 Correct 65 ms 14068 KB Correct solution.
8 Correct 54 ms 13928 KB Correct solution.

Subtask #3
15.0 / 15.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Correct solution.
2 Correct 4 ms 4940 KB Correct solution.
3 Correct 4 ms 4940 KB Correct solution.
4 Correct 4 ms 4940 KB Correct solution.
5 Correct 4 ms 4940 KB Correct solution.
6 Correct 4 ms 5068 KB Correct solution.
7 Correct 4 ms 5068 KB Correct solution.
8 Correct 4 ms 5068 KB Correct solution.
9 Correct 5 ms 5068 KB Correct solution.
10 Correct 4 ms 5068 KB Correct solution.
11 Correct 4 ms 5068 KB Correct solution.
12 Correct 21 ms 7244 KB Correct solution.
13 Correct 27 ms 7840 KB Correct solution.
14 Correct 25 ms 7276 KB Correct solution.
15 Correct 25 ms 7224 KB Correct solution.
16 Correct 25 ms 7216 KB Correct solution.
17 Correct 5 ms 5564 KB Correct solution.
18 Correct 26 ms 7500 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4980 KB Correct solution.
2 Correct 4 ms 4940 KB Correct solution.
3 Correct 3 ms 4940 KB Correct solution.
4 Correct 41 ms 14528 KB Correct solution.
5 Correct 24 ms 10496 KB Correct solution.
6 Correct 36 ms 12228 KB Correct solution.
7 Correct 57 ms 16988 KB Correct solution.
8 Correct 62 ms 19396 KB Correct solution.
9 Correct 56 ms 16324 KB Correct solution.
10 Correct 4 ms 4940 KB Correct solution.
11 Correct 4 ms 4952 KB Correct solution.
12 Correct 4 ms 4940 KB Correct solution.
13 Correct 41 ms 9000 KB Correct solution.
14 Correct 3 ms 5028 KB Correct solution.
15 Correct 9 ms 5836 KB Correct solution.
16 Correct 65 ms 14068 KB Correct solution.
17 Correct 54 ms 13928 KB Correct solution.
18 Correct 3 ms 4940 KB Correct solution.
19 Correct 4 ms 4940 KB Correct solution.
20 Correct 4 ms 4940 KB Correct solution.
21 Correct 4 ms 4940 KB Correct solution.
22 Correct 4 ms 4940 KB Correct solution.
23 Correct 4 ms 5068 KB Correct solution.
24 Correct 4 ms 5068 KB Correct solution.
25 Correct 4 ms 5068 KB Correct solution.
26 Correct 5 ms 5068 KB Correct solution.
27 Correct 4 ms 5068 KB Correct solution.
28 Correct 4 ms 5068 KB Correct solution.
29 Correct 21 ms 7244 KB Correct solution.
30 Correct 27 ms 7840 KB Correct solution.
31 Correct 25 ms 7276 KB Correct solution.
32 Correct 25 ms 7224 KB Correct solution.
33 Correct 25 ms 7216 KB Correct solution.
34 Correct 5 ms 5564 KB Correct solution.
35 Correct 26 ms 7500 KB Correct solution.
36 Correct 49 ms 12244 KB Correct solution.
37 Correct 67 ms 13640 KB Correct solution.
38 Correct 63 ms 13960 KB Correct solution.
39 Correct 66 ms 10376 KB Correct solution.
40 Correct 64 ms 10788 KB Correct solution.
41 Correct 52 ms 16232 KB Correct solution.
42 Correct 56 ms 13900 KB Correct solution.