Submission #276448

#	Time	Username	Problem	Language	Result	Execution time	Memory
276448		index_	Sleepy game (innopolis2018_final_D)	C++17	100 / 100	599 ms	59996 KiB

D

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <deque>
#include <chrono>
#include <cassert>
#include <bitset>
#include <random>

using namespace std;

typedef long long li;
typedef  long double ld;
const li MAX = 3e5 + 5;

li inf = (li)2e18;
li mod = (li)998244353;

li n, m, pos[MAX];
map<pair<li, li>, li> used;
map<pair<li, li>, vector<pair<li, li>>> gr;
vector<li> g[MAX];
li mb = 0;
vector<pair<li, li>> prv;

void out() {
    cout << "Win\n";
    for (int i = 0; i < prv.size(); i++) cout << prv[i].first << " ";
    exit(0);
}
void dfs(pair<li, li> vert) {
    used[vert] = 1;
    prv.push_back(vert);
    for (auto u : gr[vert]) {
        if (!used[u]) dfs(u);
    }
    if (gr[vert].size() == 0 && vert.second == 1) {
        out();
        exit(0);
    }
    prv.pop_back();
}

void pr(li vert) {
    cout << "Draw\n";
    exit(0);
}

void cyc(li vert) {
    pos[vert] = 1;
    for (auto u : g[vert]) {
        if (!pos[u]) cyc(u);
        else pr(vert);
    }
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        li c;
        cin >> c;
        for (int j = 0; j < c; j++) {
            li b;
            cin >> b;
            gr[{i, 0}].push_back({ b, 1 });
            gr[{i, 1}].push_back({ b, 0 });
            g[i].push_back(b);
        }
    }
    li s;
    cin >> s;
    dfs({ s, 0 });
    cyc(s);
    cout << "Lose\n";
}

int main() {
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    ios::sync_with_stdio(0);
    li q;
    q = 1;
    while (q--) solve();

    return 0;
}

Compilation message (stderr)

D.cpp: In function 'void out()':
D.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 0; i < prv.size(); i++) cout << prv[i].first << " ";
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 19 / 19
• Subtask 3: 15 / 15
• Subtask 4: 11 / 11
• Subtask 5: 38 / 38