oj.uz

Submission #282857

# Submission time Handle Problem Language Result Execution time Memory
282857 2020-08-25T05:09:39 Z 문홍윤(#5763) Sleepy game (innopolis2018_final_D) C++17
100 / 100
 104 ms 17016 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2e18;
const int inf=1e9;

int n, m, s;
pii fr[100010][2];
vector<int> link[100010];

bool ch[100010][2];

void dfs(int num, int d){
    if(ch[num][d])return;
    ch[num][d]=true;
    for(auto i:link[num]){
        if(ch[i][1-d])continue;
        fr[i][1-d]=mp(num, d);
        dfs(i, 1-d);
    }
}

void trace(int num, int d){
    if(num==s&&!d){
        printf("%d ", num);
        return;
    }
    trace(fr[num][d].F, fr[num][d].S);
    printf("%d ", num);
}

void check_win(){
    dfs(s, 0);
    for(int i=1; i<=n; i++){
        if(link[i].size())continue;
        if(ch[i][1]){
            puts("Win");
            trace(i, 1);
            exit(0);
        }
    }
}

bool ch2[100010], flg;

void dfs2(int num){
    if(ch2[num]){
        flg=true;
        return;
    }
    ch2[num]=true;
    for(auto i:link[num])dfs2(i);
}

void check_draw(){
    dfs2(s);
    if(flg){
        puts("Draw");
        exit(0);
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        int sz;
        scanf("%d", &sz);
        for(int j=1; j<=sz; j++){
            int a;
            scanf("%d", &a);
            link[i].eb(a);
        }
    }
    scanf("%d", &s);
    check_win();
    check_draw();
    puts("Lose");
}

Compilation message

D.cpp: In function 'int main()':
D.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
D.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |         scanf("%d", &sz);
      |         ~~~~~^~~~~~~~~~~
D.cpp:81:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |             scanf("%d", &a);
      |             ~~~~~^~~~~~~~~~
D.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |     scanf("%d", &s);
      |     ~~~~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 2 ms 2688 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 64 ms 12280 KB Correct solution.
5 Correct 32 ms 8184 KB Correct solution.
6 Correct 47 ms 9976 KB Correct solution.
7 Correct 73 ms 14456 KB Correct solution.
8 Correct 80 ms 17016 KB Correct solution.
9 Correct 70 ms 13984 KB Correct solution.

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 2 ms 2688 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 65 ms 5468 KB Correct solution.
5 Correct 2 ms 2560 KB Correct solution.
6 Correct 9 ms 3456 KB Correct solution.
7 Correct 90 ms 11000 KB Correct solution.
8 Correct 76 ms 11252 KB Correct solution.

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 2 ms 2688 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 2 ms 2688 KB Correct solution.
5 Correct 2 ms 2688 KB Correct solution.
6 Correct 3 ms 2816 KB Correct solution.
7 Correct 3 ms 2816 KB Correct solution.
8 Correct 3 ms 2688 KB Correct solution.
9 Correct 3 ms 2688 KB Correct solution.
10 Correct 2 ms 2816 KB Correct solution.
11 Correct 3 ms 2688 KB Correct solution.

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 2 ms 2688 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 2 ms 2688 KB Correct solution.
5 Correct 2 ms 2688 KB Correct solution.
6 Correct 3 ms 2816 KB Correct solution.
7 Correct 3 ms 2816 KB Correct solution.
8 Correct 3 ms 2688 KB Correct solution.
9 Correct 3 ms 2688 KB Correct solution.
10 Correct 2 ms 2816 KB Correct solution.
11 Correct 3 ms 2688 KB Correct solution.
12 Correct 28 ms 4344 KB Correct solution.
13 Correct 35 ms 4600 KB Correct solution.
14 Correct 37 ms 4088 KB Correct solution.
15 Correct 34 ms 3968 KB Correct solution.
16 Correct 36 ms 3960 KB Correct solution.
17 Correct 4 ms 3200 KB Correct solution.
18 Correct 32 ms 4216 KB Correct solution.

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Correct solution.
2 Correct 2 ms 2688 KB Correct solution.
3 Correct 2 ms 2688 KB Correct solution.
4 Correct 64 ms 12280 KB Correct solution.
5 Correct 32 ms 8184 KB Correct solution.
6 Correct 47 ms 9976 KB Correct solution.
7 Correct 73 ms 14456 KB Correct solution.
8 Correct 80 ms 17016 KB Correct solution.
9 Correct 70 ms 13984 KB Correct solution.
10 Correct 2 ms 2688 KB Correct solution.
11 Correct 2 ms 2688 KB Correct solution.
12 Correct 2 ms 2688 KB Correct solution.
13 Correct 65 ms 5468 KB Correct solution.
14 Correct 2 ms 2560 KB Correct solution.
15 Correct 9 ms 3456 KB Correct solution.
16 Correct 90 ms 11000 KB Correct solution.
17 Correct 76 ms 11252 KB Correct solution.
18 Correct 2 ms 2688 KB Correct solution.
19 Correct 2 ms 2688 KB Correct solution.
20 Correct 2 ms 2688 KB Correct solution.
21 Correct 2 ms 2688 KB Correct solution.
22 Correct 2 ms 2688 KB Correct solution.
23 Correct 3 ms 2816 KB Correct solution.
24 Correct 3 ms 2816 KB Correct solution.
25 Correct 3 ms 2688 KB Correct solution.
26 Correct 3 ms 2688 KB Correct solution.
27 Correct 2 ms 2816 KB Correct solution.
28 Correct 3 ms 2688 KB Correct solution.
29 Correct 28 ms 4344 KB Correct solution.
30 Correct 35 ms 4600 KB Correct solution.
31 Correct 37 ms 4088 KB Correct solution.
32 Correct 34 ms 3968 KB Correct solution.
33 Correct 36 ms 3960 KB Correct solution.
34 Correct 4 ms 3200 KB Correct solution.
35 Correct 32 ms 4216 KB Correct solution.
36 Correct 72 ms 9592 KB Correct solution.
37 Correct 89 ms 10744 KB Correct solution.
38 Correct 96 ms 11128 KB Correct solution.
39 Correct 99 ms 7672 KB Correct solution.
40 Correct 104 ms 7800 KB Correct solution.
41 Correct 79 ms 13840 KB Correct solution.
42 Correct 79 ms 10872 KB Correct solution.