oj.uz

Submission #276448

# Submission time Handle Problem Language Result Execution time Memory
276448 2020-08-20T12:55:19 Z index_ Sleepy game (innopolis2018_final_D) C++17
100 / 100
 599 ms 59996 KB 
//#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Correct solution.
2 Correct 6 ms 7424 KB Correct solution.
3 Correct 5 ms 7424 KB Correct solution.
4 Correct 352 ms 42912 KB Correct solution.
5 Correct 182 ms 28692 KB Correct solution.
6 Correct 243 ms 36204 KB Correct solution.
7 Correct 331 ms 51092 KB Correct solution.
8 Correct 599 ms 59996 KB Correct solution.
9 Correct 439 ms 51340 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Correct solution.
2 Correct 5 ms 7424 KB Correct solution.
3 Correct 6 ms 7424 KB Correct solution.
4 Correct 142 ms 33656 KB Correct solution.
5 Correct 5 ms 7424 KB Correct solution.
6 Correct 27 ms 11680 KB Correct solution.
7 Correct 378 ms 50280 KB Correct solution.
8 Correct 478 ms 50280 KB Correct solution.

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Correct solution.
2 Correct 5 ms 7424 KB Correct solution.
3 Correct 5 ms 7424 KB Correct solution.
4 Correct 6 ms 7552 KB Correct solution.
5 Correct 5 ms 7424 KB Correct solution.
6 Correct 7 ms 7680 KB Correct solution.
7 Correct 8 ms 7808 KB Correct solution.
8 Correct 7 ms 7808 KB Correct solution.
9 Correct 7 ms 7808 KB Correct solution.
10 Correct 7 ms 7808 KB Correct solution.
11 Correct 6 ms 7808 KB Correct solution.

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Correct solution.
2 Correct 5 ms 7424 KB Correct solution.
3 Correct 5 ms 7424 KB Correct solution.
4 Correct 6 ms 7552 KB Correct solution.
5 Correct 5 ms 7424 KB Correct solution.
6 Correct 7 ms 7680 KB Correct solution.
7 Correct 8 ms 7808 KB Correct solution.
8 Correct 7 ms 7808 KB Correct solution.
9 Correct 7 ms 7808 KB Correct solution.
10 Correct 7 ms 7808 KB Correct solution.
11 Correct 6 ms 7808 KB Correct solution.
12 Correct 118 ms 19576 KB Correct solution.
13 Correct 146 ms 23060 KB Correct solution.
14 Correct 81 ms 20344 KB Correct solution.
15 Correct 58 ms 20856 KB Correct solution.
16 Correct 92 ms 21112 KB Correct solution.
17 Correct 14 ms 9600 KB Correct solution.
18 Correct 61 ms 22140 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Correct solution.
2 Correct 6 ms 7424 KB Correct solution.
3 Correct 5 ms 7424 KB Correct solution.
4 Correct 352 ms 42912 KB Correct solution.
5 Correct 182 ms 28692 KB Correct solution.
6 Correct 243 ms 36204 KB Correct solution.
7 Correct 331 ms 51092 KB Correct solution.
8 Correct 599 ms 59996 KB Correct solution.
9 Correct 439 ms 51340 KB Correct solution.
10 Correct 5 ms 7424 KB Correct solution.
11 Correct 5 ms 7424 KB Correct solution.
12 Correct 6 ms 7424 KB Correct solution.
13 Correct 142 ms 33656 KB Correct solution.
14 Correct 5 ms 7424 KB Correct solution.
15 Correct 27 ms 11680 KB Correct solution.
16 Correct 378 ms 50280 KB Correct solution.
17 Correct 478 ms 50280 KB Correct solution.
18 Correct 5 ms 7424 KB Correct solution.
19 Correct 5 ms 7424 KB Correct solution.
20 Correct 5 ms 7424 KB Correct solution.
21 Correct 6 ms 7552 KB Correct solution.
22 Correct 5 ms 7424 KB Correct solution.
23 Correct 7 ms 7680 KB Correct solution.
24 Correct 8 ms 7808 KB Correct solution.
25 Correct 7 ms 7808 KB Correct solution.
26 Correct 7 ms 7808 KB Correct solution.
27 Correct 7 ms 7808 KB Correct solution.
28 Correct 6 ms 7808 KB Correct solution.
29 Correct 118 ms 19576 KB Correct solution.
30 Correct 146 ms 23060 KB Correct solution.
31 Correct 81 ms 20344 KB Correct solution.
32 Correct 58 ms 20856 KB Correct solution.
33 Correct 92 ms 21112 KB Correct solution.
34 Correct 14 ms 9600 KB Correct solution.
35 Correct 61 ms 22140 KB Correct solution.
36 Correct 106 ms 31432 KB Correct solution.
37 Correct 123 ms 35576 KB Correct solution.
38 Correct 363 ms 50372 KB Correct solution.
39 Correct 131 ms 38392 KB Correct solution.
40 Correct 409 ms 44920 KB Correct solution.
41 Correct 502 ms 51172 KB Correct solution.
42 Correct 273 ms 47976 KB Correct solution.