oj.uz

Submission #142639

# Submission time Handle Problem Language Result Execution time Memory
142639 2019-08-10T07:38:25 Z meatrow Sleepy game (innopolis2018_final_D) C++17
100 / 100
 99 ms 12780 KB 
//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;

const int N = 1e5 + 5;

int dist[N][2];
int way[N][2];
vector<int> g[N];
int used[N];
int cycle;

void dfs(int v) {
    used[v] = 1;
    for (int u : g[v]) {
        if (used[u] == 1) {
            cycle = 1;
        }
        if (!used[u]) {
            dfs(u);
        }
    }
    used[v] = 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int v;
            cin >> v;
            g[i].push_back(v);
        }
    }
    int st;
    cin >> st;
    dfs(st);
    dist[st][0] = 1;
    queue<pair<int, int>> q;
    q.push({ st, 0 });
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        for (int u : g[p.first]) {
            if (!dist[u][p.second ^ 1]) {
                way[u][p.second ^ 1] = p.first;
                dist[u][p.second ^ 1] = 1;
                q.push({ u, p.second ^ 1 });
            }
        }
    }
    int kek = 0;
    for (int i = 1; i <= n; i++) {
        if (g[i].empty() && dist[i][1]) {
            kek = i;
        }
    }
    if (kek) {
        cout << "Win\n";
        vector<int> path;
        int t = 1;
        for (; kek; kek = way[kek][t], t ^= 1) {
            path.push_back(kek);
        }
        reverse(path.begin(), path.end());
        for (int v : path) {
            cout << v << ' ';
        }
        return 0;
    }
    if (cycle) {
        cout << "Draw";
    } else {
        cout << "Lose";
    }
    return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Correct solution.
2 Correct 4 ms 2680 KB Correct solution.
3 Correct 4 ms 2680 KB Correct solution.
4 Correct 61 ms 9336 KB Correct solution.
5 Correct 36 ms 7160 KB Correct solution.
6 Correct 50 ms 9208 KB Correct solution.
7 Correct 87 ms 12780 KB Correct solution.
8 Correct 98 ms 11640 KB Correct solution.
9 Correct 80 ms 11640 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Correct solution.
2 Correct 4 ms 2680 KB Correct solution.
3 Correct 4 ms 2680 KB Correct solution.
4 Correct 47 ms 6924 KB Correct solution.
5 Correct 5 ms 2680 KB Correct solution.
6 Correct 11 ms 3576 KB Correct solution.
7 Correct 89 ms 11380 KB Correct solution.
8 Correct 79 ms 11460 KB Correct solution.

Subtask #3
15.0 / 15.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Correct solution.
2 Correct 4 ms 2680 KB Correct solution.
3 Correct 4 ms 2680 KB Correct solution.
4 Correct 4 ms 2680 KB Correct solution.
5 Correct 4 ms 2680 KB Correct solution.
6 Correct 6 ms 2808 KB Correct solution.
7 Correct 5 ms 2808 KB Correct solution.
8 Correct 5 ms 2808 KB Correct solution.
9 Correct 5 ms 2808 KB Correct solution.
10 Correct 5 ms 2808 KB Correct solution.
11 Correct 5 ms 2808 KB Correct solution.
12 Correct 27 ms 4704 KB Correct solution.
13 Correct 32 ms 5240 KB Correct solution.
14 Correct 30 ms 4984 KB Correct solution.
15 Correct 32 ms 4984 KB Correct solution.
16 Correct 30 ms 4984 KB Correct solution.
17 Correct 6 ms 3064 KB Correct solution.
18 Correct 29 ms 5240 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Correct solution.
2 Correct 4 ms 2680 KB Correct solution.
3 Correct 4 ms 2680 KB Correct solution.
4 Correct 61 ms 9336 KB Correct solution.
5 Correct 36 ms 7160 KB Correct solution.
6 Correct 50 ms 9208 KB Correct solution.
7 Correct 87 ms 12780 KB Correct solution.
8 Correct 98 ms 11640 KB Correct solution.
9 Correct 80 ms 11640 KB Correct solution.
10 Correct 4 ms 2680 KB Correct solution.
11 Correct 4 ms 2680 KB Correct solution.
12 Correct 4 ms 2680 KB Correct solution.
13 Correct 47 ms 6924 KB Correct solution.
14 Correct 5 ms 2680 KB Correct solution.
15 Correct 11 ms 3576 KB Correct solution.
16 Correct 89 ms 11380 KB Correct solution.
17 Correct 79 ms 11460 KB Correct solution.
18 Correct 4 ms 2680 KB Correct solution.
19 Correct 4 ms 2680 KB Correct solution.
20 Correct 4 ms 2680 KB Correct solution.
21 Correct 4 ms 2680 KB Correct solution.
22 Correct 4 ms 2680 KB Correct solution.
23 Correct 6 ms 2808 KB Correct solution.
24 Correct 5 ms 2808 KB Correct solution.
25 Correct 5 ms 2808 KB Correct solution.
26 Correct 5 ms 2808 KB Correct solution.
27 Correct 5 ms 2808 KB Correct solution.
28 Correct 5 ms 2808 KB Correct solution.
29 Correct 27 ms 4704 KB Correct solution.
30 Correct 32 ms 5240 KB Correct solution.
31 Correct 30 ms 4984 KB Correct solution.
32 Correct 32 ms 4984 KB Correct solution.
33 Correct 30 ms 4984 KB Correct solution.
34 Correct 6 ms 3064 KB Correct solution.
35 Correct 29 ms 5240 KB Correct solution.
36 Correct 69 ms 8832 KB Correct solution.
37 Correct 80 ms 9996 KB Correct solution.
38 Correct 94 ms 11392 KB Correct solution.
39 Correct 98 ms 9332 KB Correct solution.
40 Correct 88 ms 9300 KB Correct solution.
41 Correct 99 ms 11720 KB Correct solution.
42 Correct 75 ms 10744 KB Correct solution.