Submission #366579

#	Time	Username	Problem	Language	Result	Execution time	Memory
366579		haboh	Sleepy game (innopolis2018_final_D)	C++14	100 / 100	126 ms	10892 KiB

D

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