CSES - Aalto Competitive Programming 2024 - wk7 - Mon - Results
Submission details
Task:Snakeless path
Sender:Rasse
Submission time:2024-10-21 17:19:17 +0300
Language:C++ (C++11)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.00 sdetails
#31ACCEPTED0.00 sdetails
#32ACCEPTED0.00 sdetails
#33ACCEPTED0.00 sdetails
#34ACCEPTED0.01 sdetails
#35ACCEPTED0.00 sdetails
#36ACCEPTED0.00 sdetails
#37ACCEPTED0.00 sdetails
#38ACCEPTED0.01 sdetails
#39ACCEPTED0.00 sdetails
#40ACCEPTED0.00 sdetails
#41ACCEPTED0.00 sdetails
#42ACCEPTED0.00 sdetails
#43ACCEPTED0.00 sdetails
#44ACCEPTED0.01 sdetails
#45ACCEPTED0.00 sdetails
#46ACCEPTED0.00 sdetails
#47ACCEPTED0.00 sdetails
#48ACCEPTED0.01 sdetails
#49ACCEPTED0.00 sdetails
#50ACCEPTED0.01 sdetails
#51ACCEPTED0.01 sdetails
#52ACCEPTED0.01 sdetails
#53ACCEPTED0.01 sdetails
#54ACCEPTED0.15 sdetails
#55ACCEPTED0.01 sdetails
#56ACCEPTED0.02 sdetails
#57ACCEPTED0.00 sdetails
#58ACCEPTED0.15 sdetails
#59ACCEPTED0.00 sdetails
#60ACCEPTED0.20 sdetails
#61ACCEPTED0.00 sdetails
#62ACCEPTED0.00 sdetails
#63ACCEPTED0.14 sdetails
#64ACCEPTED0.01 sdetails
#65ACCEPTED0.06 sdetails
#66ACCEPTED0.01 sdetails
#67ACCEPTED0.01 sdetails
#68ACCEPTED0.15 sdetails
#69ACCEPTED0.00 sdetails
#70ACCEPTED0.13 sdetails
#71ACCEPTED0.13 sdetails
#72ACCEPTED0.13 sdetails
#73ACCEPTED0.13 sdetails
#74ACCEPTED0.24 sdetails
#75ACCEPTED0.12 sdetails
#76ACCEPTED0.25 sdetails
#77ACCEPTED0.07 sdetails
#78ACCEPTED0.04 sdetails
#79ACCEPTED0.07 sdetails
#80ACCEPTED0.10 sdetails
#81ACCEPTED0.09 sdetails
#82ACCEPTED0.08 sdetails
#83ACCEPTED0.17 sdetails
#84ACCEPTED0.13 sdetails
#85ACCEPTED0.22 sdetails
#86ACCEPTED0.11 sdetails
#87ACCEPTED0.12 sdetails
#88ACCEPTED0.05 sdetails
#89ACCEPTED0.08 sdetails

Compiler report

input/code.cpp: In function 'bool dfs(int)':
input/code.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::queue<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     while (loops < nodes.size())
      |            ~~~~~~^~~~~~~~~~~~~~

Code

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <climits>
#include <cmath>
 
//#define int long long
using namespace std;

vector<bool> visited;
vector<unordered_set<int>> adj;
int N;
vector<int> res;
queue<int> nodes;

bool dfs(int node)
{
    //cout << "checking node " << node << " ";
    node = nodes.front();
    nodes.pop();
    if (node == N-1)
    {
        res.push_back(node);
        return true;
    }
    visited[node] = true;
    int loops = 0;
    while (loops < nodes.size())
    {
        loops++;
        int i = nodes.front();
        if (adj[node].find(i) != adj[node].end())
        {
            nodes.pop();
            nodes.push(i);
            continue;
        }

        if (dfs(i))
        {
            res.push_back(node);
            return true;
        }
        loops = 0;

        //if (!visited[i])
        //{
        //}
    }

    return false;
}

void solve() {
    int m;
    cin >> N >> m;

    visited.resize(N);
    res = vector<int>();
    adj = vector<unordered_set<int>>(N, unordered_set<int>());
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--;b--;
        adj[a].insert(b);
        adj[b].insert(a);
    }
    
    for (int i = 0; i < N; i++)
    {
        nodes.push(i);
    }

    if (!dfs(0))
        cout << 0;
    else
    {
        cout << res.size() << '\n';
        for (int i = res.size() - 1; i >= 0; i--)
            cout << res[i]+1 << " ";
    }
}


 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
 
    //cin >> t;
 
    for (int i = 0; i < t; i++)
        solve();
 
    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
2 1
1 2

correct output
0

user output
0

Test 2

Verdict: ACCEPTED

input
3 1
1 3

correct output
3
1 2 3 

user output
3
1 2 3 

Test 3

Verdict: ACCEPTED

input
3 1
1 3

correct output
3
1 2 3 

user output
3
1 2 3 

Test 4

Verdict: ACCEPTED

input
3 1
1 3

correct output
3
1 2 3 

user output
3
1 2 3 

Test 5

Verdict: ACCEPTED

input
4 1
1 4

correct output
3
1 3 4 

user output
4
1 2 3 4 

Test 6

Verdict: ACCEPTED

input
4 5
1 2
1 3
1 4
2 3
...

correct output
0

user output
0

Test 7

Verdict: ACCEPTED

input
4 3
1 2
1 3
1 4

correct output
0

user output
0

Test 8

Verdict: ACCEPTED

input
4 2
1 3
2 3

correct output
2
1 4 

user output
3
1 2 4 

Test 9

Verdict: ACCEPTED

input
4 4
1 2
1 4
2 3
3 4

correct output
0

user output
0

Test 10

Verdict: ACCEPTED

input
5 6
1 2
1 4
1 5
2 5
...

correct output
5
1 3 2 4 5 

user output
5
1 3 2 4 5 

Test 11

Verdict: ACCEPTED

input
5 5
1 2
1 3
1 5
2 5
...

correct output
3
1 4 5 

user output
3
1 4 5 

Test 12

Verdict: ACCEPTED

input
5 5
1 3
1 4
1 5
3 5
...

correct output
3
1 2 5 

user output
3
1 2 5 

Test 13

Verdict: ACCEPTED

input
5 6
1 3
1 4
1 5
2 4
...

correct output
5
1 2 3 4 5 

user output
5
1 2 3 4 5 

Test 14

Verdict: ACCEPTED

input
5 9
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 15

Verdict: ACCEPTED

input
5 7
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 16

Verdict: ACCEPTED

input
5 1
1 5

correct output
3
1 4 5 

user output
5
1 2 3 4 5 

Test 17

Verdict: ACCEPTED

input
5 4
1 2
1 3
1 4
1 5

correct output
0

user output
0

Test 18

Verdict: ACCEPTED

input
5 9
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 19

Verdict: ACCEPTED

input
5 4
1 2
1 3
1 4
1 5

correct output
0

user output
0

Test 20

Verdict: ACCEPTED

input
10 16
1 2
1 3
1 4
1 5
...

correct output
6
1 6 9 8 7 10 

user output
10
1 6 8 9 2 3 4 5 7 10 

Test 21

Verdict: ACCEPTED

input
10 16
1 2
1 3
1 4
1 5
...

correct output
5
1 9 8 7 10 

user output
9
1 9 2 3 4 5 6 7 10 

Test 22

Verdict: ACCEPTED

input
10 16
1 2
1 4
1 5
1 6
...

correct output
10
1 3 9 8 7 6 5 4 2 10 

user output
10
1 3 4 5 6 7 8 9 2 10 

Test 23

Verdict: ACCEPTED

input
10 16
1 3
1 4
1 5
1 6
...

correct output
6
1 2 9 8 7 10 

user output
8
1 2 3 4 5 6 7 10 

Test 24

Verdict: ACCEPTED

input
10 39
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 25

Verdict: ACCEPTED

input
10 17
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 26

Verdict: ACCEPTED

input
10 1
1 10

correct output
3
1 9 10 

user output
10
1 2 3 4 5 6 7 8 9 10 

Test 27

Verdict: ACCEPTED

input
10 9
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 28

Verdict: ACCEPTED

input
10 40
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 29

Verdict: ACCEPTED

input
10 9
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 30

Verdict: ACCEPTED

input
100 196
1 2
1 3
1 4
1 5
...

correct output
31
1 60 99 98 97 96 95 94 93 92 9...

user output
15
1 60 61 62 63 64 65 66 67 68 6...

Test 31

Verdict: ACCEPTED

input
100 196
1 2
1 3
1 4
1 5
...

correct output
30
1 99 98 97 96 95 94 93 92 91 9...

user output
74
1 99 2 3 4 5 6 7 8 9 10 11 12 ...
Truncated

Test 32

Verdict: ACCEPTED

input
100 196
1 2
1 3
1 4
1 5
...

correct output
98
1 20 99 98 97 96 95 94 93 92 9...

user output
85
1 20 21 22 23 24 25 26 27 28 2...
Truncated

Test 33

Verdict: ACCEPTED

input
100 196
1 2
1 3
1 4
1 5
...

correct output
32
1 8 99 98 97 96 95 94 93 92 91...

user output
66
1 8 9 10 11 12 13 14 15 16 17 ...
Truncated

Test 34

Verdict: ACCEPTED

input
100 4910
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 35

Verdict: ACCEPTED

input
100 197
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 36

Verdict: ACCEPTED

input
100 248
1 8
1 29
1 53
1 61
...

correct output
3
1 99 100 

user output
93
1 2 3 4 5 6 7 8 9 12 13 14 15 ...
Truncated

Test 37

Verdict: ACCEPTED

input
100 99
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 38

Verdict: ACCEPTED

input
100 4888
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 39

Verdict: ACCEPTED

input
100 99
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 40

Verdict: ACCEPTED

input
200 396
1 2
1 3
1 4
1 5
...

correct output
60
1 119 199 198 197 196 195 194 ...

user output
27
1 119 120 121 122 123 124 125 ...
Truncated

Test 41

Verdict: ACCEPTED

input
200 396
1 2
1 3
1 4
1 5
...

correct output
58
1 199 198 197 196 195 194 193 ...

user output
146
1 199 2 3 4 5 6 7 8 9 10 11 12...
Truncated

Test 42

Verdict: ACCEPTED

input
200 396
1 2
1 3
1 4
1 5
...

correct output
195
1 38 199 198 197 196 195 194 1...

user output
170
1 38 39 40 41 42 43 44 45 46 4...
Truncated

Test 43

Verdict: ACCEPTED

input
200 396
1 2
1 3
1 4
1 5
...

correct output
61
1 16 199 198 197 196 195 194 1...

user output
129
1 16 17 18 19 20 21 22 23 24 2...
Truncated

Test 44

Verdict: ACCEPTED

input
200 19807
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 45

Verdict: ACCEPTED

input
200 397
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 46

Verdict: ACCEPTED

input
200 994
1 8
1 29
1 53
1 61
...

correct output
3
1 199 200 

user output
192
1 2 3 4 6 8 9 10 11 12 13 14 1...
Truncated

Test 47

Verdict: ACCEPTED

input
200 199
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 48

Verdict: ACCEPTED

input
200 19792
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 49

Verdict: ACCEPTED

input
200 199
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 50

Verdict: ACCEPTED

input
1000 1996
1 2
1 3
1 4
1 5
...

correct output
288
1 593 999 998 997 996 995 994 ...

user output
125
1 593 594 595 596 597 598 599 ...
Truncated

Test 51

Verdict: ACCEPTED

input
1000 1996
1 2
1 3
1 4
1 5
...

correct output
282
1 997 999 998 996 995 994 993 ...

user output
724
1 997 998 999 2 3 4 5 6 7 8 9 ...
Truncated

Test 52

Verdict: ACCEPTED

input
1000 1996
1 2
1 3
1 4
1 5
...

correct output
975
1 186 999 998 997 996 995 994 ...

user output
842
1 186 187 188 189 190 191 192 ...
Truncated

Test 53

Verdict: ACCEPTED

input
1000 1996
1 2
1 3
1 4
1 5
...

correct output
295
1 72 999 998 997 996 995 994 9...

user output
639
1 72 73 74 75 76 77 78 79 80 8...
Truncated

Test 54

Verdict: ACCEPTED

input
1000 299999
1 2
1 3
1 4
1 5
...

correct output
3
1 691 1000 

user output
311
1 691 692 693 694 695 696 697 ...
Truncated

Test 55

Verdict: ACCEPTED

input
1000 1997
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 56

Verdict: ACCEPTED

input
1000 25751
1 8
1 29
1 53
1 61
...

correct output
4
1 999 998 1000 

user output
998
1 2 3 5 6 7 8 9 10 11 12 13 14...
Truncated

Test 57

Verdict: ACCEPTED

input
1000 999
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 58

Verdict: ACCEPTED

input
1000 299999
1 2
1 3
1 4
1 5
...

correct output
3
1 832 1000 

user output
170
1 832 833 834 835 836 837 838 ...
Truncated

Test 59

Verdict: ACCEPTED

input
1000 999
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 60

Verdict: ACCEPTED

input
1000 299999
1 2
1 3
1 4
1 5
...

correct output
3
1 999 1000 

user output
580
1 9 12 13 19 20 22 23 25 28 30...
Truncated

Test 61

Verdict: ACCEPTED

input
1000 999
1 1000
2 1000
3 1000
4 1000
...

correct output
0

user output
0

Test 62

Verdict: ACCEPTED

input
1000 999
1 1000
2 1000
3 1000
4 1000
...

correct output
0

user output
0

Test 63

Verdict: ACCEPTED

input
1000 195765
1 2
1 3
1 4
1 5
...

correct output
4
1 999 997 1000 

user output
940
1 6 7 9 10 13 16 18 19 20 21 2...
Truncated

Test 64

Verdict: ACCEPTED

input
1000 1996
1 2
1 3
1 4
1 5
...

correct output
229
1 922 999 998 997 996 995 994 ...

user output
852
1 922 923 924 925 926 927 928 ...
Truncated

Test 65

Verdict: ACCEPTED

input
1000 92979
1 6
1 8
1 12
1 18
...

correct output
2
1 1000 

user output
811
1 2 3 4 6 8 9 10 11 13 14 15 1...
Truncated

Test 66

Verdict: ACCEPTED

input
1000 1997
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 67

Verdict: ACCEPTED

input
1000 1997
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 68

Verdict: ACCEPTED

input
1000 299999
1 2
1 3
1 4
1 5
...

correct output
3
1 885 1000 

user output
117
1 885 886 887 888 889 890 891 ...
Truncated

Test 69

Verdict: ACCEPTED

input
1000 999
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 70

Verdict: ACCEPTED

input
100000 199996
1 2
1 3
1 4
1 5
...

correct output
28483
1 59286 99999 99998 99997 9999...

user output
12237
1 59286 59287 59288 59289 5929...
Truncated

Test 71

Verdict: ACCEPTED

input
100000 199996
1 2
1 3
1 4
1 5
...

correct output
27969
1 99719 99999 99998 99997 9999...

user output
72315
1 99719 99720 99721 99722 9972...
Truncated

Test 72

Verdict: ACCEPTED

input
100000 199996
1 2
1 3
1 4
1 5
...

correct output
97408
1 18510 99999 99998 99997 9999...

user output
84085
1 18510 18511 18512 18513 1851...
Truncated

Test 73

Verdict: ACCEPTED

input
100000 199996
1 2
1 3
1 4
1 5
...

correct output
29187
1 7074 99999 99998 99997 99996...

user output
63745
1 7074 7075 7076 7077 7078 707...
Truncated

Test 74

Verdict: ACCEPTED

input
100000 270197
1 861
1 12080
1 39541
1 39686
...

correct output
3
1 99999 100000 

user output
99995
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Truncated

Test 75

Verdict: ACCEPTED

input
100000 199997
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 76

Verdict: ACCEPTED

input
100000 284253
1 23553
1 48406
1 56616
1 56899
...

correct output
2
1 100000 

user output
99994
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Truncated

Test 77

Verdict: ACCEPTED

input
100000 99999
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 78

Verdict: ACCEPTED

input
100000 3335
1 100000
11 26761
12 80933
41 44903
...

correct output
3
1 99999 100000 

user output
100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Truncated

Test 79

Verdict: ACCEPTED

input
100000 99999
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 80

Verdict: ACCEPTED

input
100000 89632
1 76350
1 97733
1 100000
2 16314
...

correct output
3
1 99999 100000 

user output
99999
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Truncated

Test 81

Verdict: ACCEPTED

input
100000 99999
1 100000
2 100000
3 100000
4 100000
...

correct output
0

user output
0

Test 82

Verdict: ACCEPTED

input
100000 99999
1 100000
2 100000
3 100000
4 100000
...

correct output
0

user output
0

Test 83

Verdict: ACCEPTED

input
100000 182210
1 17827
1 55463
1 98875
1 100000
...

correct output
3
1 99999 100000 

user output
99994
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Truncated

Test 84

Verdict: ACCEPTED

input
100000 199996
1 2
1 3
1 4
1 5
...

correct output
22685
1 92190 99999 99998 99997 9999...

user output
85128
1 92190 92191 92192 92193 9219...
Truncated

Test 85

Verdict: ACCEPTED

input
100000 244084
1 33037
1 48376
1 94522
1 100000
...

correct output
3
1 99999 100000 

user output
99992
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Truncated

Test 86

Verdict: ACCEPTED

input
100000 199997
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 87

Verdict: ACCEPTED

input
100000 199997
1 2
1 3
1 4
1 5
...

correct output
0

user output
0

Test 88

Verdict: ACCEPTED

input
100000 22805
1 100000
2 29973
7 38479
7 77260
...

correct output
3
1 99999 100000 

user output
100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Truncated

Test 89

Verdict: ACCEPTED

input
100000 99999
1 2
1 3
1 4
1 5
...

correct output
0

user output
0