Submission #142639

#	Time	Username	Problem	Language	Result	Execution time	Memory
142639		meatrow	Sleepy game (innopolis2018_final_D)	C++17	100 / 100	99 ms	12780 KiB

D

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