oj.uz

Submission #366579

# Submission time Handle Problem Language Result Execution time Memory
366579 2021-02-14T16:17:12 Z haboh Sleepy game (innopolis2018_final_D) C++14
100 / 100
 126 ms 10892 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int>g[100100];

bool dest[100100][2];
int p[100100][2];

bool used[100100];

void dfs(int v) {
    used[v] = true;
    for (int u:g[v]){
        if(used[u]) {
            cout << "Draw";
            exit(0);
        }
        dfs(u);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int v = 1; v <= n; v++) {
        int c;
        cin >> c;
        for (;c;c--) {
            int u;
            cin >> u;
            g[v].push_back(u);
        }
    }
    int s;
    cin >> s;
    dest[s][0] = true;
    queue<pair<int,int>>q;
    q.push({s,0});
    p[s][0] = -1;
    while(q.size()){
        int v = q.front().first;
        int odd = q.front().second;
        q.pop();
        for (int u : g[v]) {
            if(!dest[u][odd ^ 1]){
                dest[u][odd ^ 1] = true;
                p[u][odd ^ 1] = v;
                q.push({u, odd ^ 1});
            }
        }
    }
    
    for(int v=1;v<=n;v++){
        if(dest[v][1]==true && g[v].size() == 0) {
            cout << "Win\n";
            int odd = 1;
            vector<int>ans;
            while (v != -1) {
                ans.push_back(v);
                v = p[v][odd];
                odd ^= 1;
            }
            reverse(ans.begin(),ans.end());
            for (int x : ans) {
                cout << x << " ";
            }

            return 0;
        }
    }

    dfs(s);

    cout << "Lose";
    return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Correct solution.
2 Correct 2 ms 2668 KB Correct solution.
3 Correct 2 ms 2668 KB Correct solution.
4 Correct 69 ms 8556 KB Correct solution.
5 Correct 38 ms 6636 KB Correct solution.
6 Correct 64 ms 8300 KB Correct solution.
7 Correct 94 ms 8684 KB Correct solution.
8 Correct 110 ms 10732 KB Correct solution.
9 Correct 97 ms 10732 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Correct solution.
2 Correct 2 ms 2668 KB Correct solution.
3 Correct 2 ms 2668 KB Correct solution.
4 Correct 89 ms 6764 KB Correct solution.
5 Correct 2 ms 2668 KB Correct solution.
6 Correct 15 ms 3308 KB Correct solution.
7 Correct 126 ms 8916 KB Correct solution.
8 Correct 93 ms 8936 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 2 ms 2668 KB Correct solution.
5 Correct 2 ms 2668 KB Correct solution.
6 Correct 3 ms 2796 KB Correct solution.
7 Correct 3 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 2 ms 2668 KB Correct solution.
5 Correct 2 ms 2668 KB Correct solution.
6 Correct 3 ms 2796 KB Correct solution.
7 Correct 3 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 47 ms 4460 KB Correct solution.
13 Correct 60 ms 5100 KB Correct solution.
14 Correct 58 ms 4844 KB Correct solution.
15 Correct 57 ms 4972 KB Correct solution.
16 Correct 58 ms 4972 KB Correct solution.
17 Correct 5 ms 3052 KB Correct solution.
18 Correct 56 ms 5100 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Correct solution.
2 Correct 2 ms 2668 KB Correct solution.
3 Correct 2 ms 2668 KB Correct solution.
4 Correct 69 ms 8556 KB Correct solution.
5 Correct 38 ms 6636 KB Correct solution.
6 Correct 64 ms 8300 KB Correct solution.
7 Correct 94 ms 8684 KB Correct solution.
8 Correct 110 ms 10732 KB Correct solution.
9 Correct 97 ms 10732 KB Correct solution.
10 Correct 3 ms 2668 KB Correct solution.
11 Correct 2 ms 2668 KB Correct solution.
12 Correct 2 ms 2668 KB Correct solution.
13 Correct 89 ms 6764 KB Correct solution.
14 Correct 2 ms 2668 KB Correct solution.
15 Correct 15 ms 3308 KB Correct solution.
16 Correct 126 ms 8916 KB Correct solution.
17 Correct 93 ms 8936 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 2 ms 2668 KB Correct solution.
22 Correct 2 ms 2668 KB Correct solution.
23 Correct 3 ms 2796 KB Correct solution.
24 Correct 3 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 47 ms 4460 KB Correct solution.
30 Correct 60 ms 5100 KB Correct solution.
31 Correct 58 ms 4844 KB Correct solution.
32 Correct 57 ms 4972 KB Correct solution.
33 Correct 58 ms 4972 KB Correct solution.
34 Correct 5 ms 3052 KB Correct solution.
35 Correct 56 ms 5100 KB Correct solution.
36 Correct 99 ms 7276 KB Correct solution.
37 Correct 113 ms 8044 KB Correct solution.
38 Correct 116 ms 8936 KB Correct solution.
39 Correct 126 ms 8300 KB Correct solution.
40 Correct 110 ms 8312 KB Correct solution.
41 Correct 99 ms 10892 KB Correct solution.
42 Correct 112 ms 9920 KB Correct solution.