CSES - Datatähti 2024 loppu - Results
Submission details
Task:Polut
Sender:andreibe
Submission time:2024-01-20 16:07:03 +0200
Language:C++11
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.01 s1, 2, 3details
#20.01 s1, 2, 3details
#30.01 s1, 2, 3details
#40.01 s1, 2, 3details
#50.01 s1, 2, 3details
#60.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#80.01 s1, 2, 3details
#90.01 s1, 2, 3details
#100.01 s1, 2, 3details
#110.01 s1, 2, 3details
#120.02 s2, 3details
#130.02 s2, 3details
#140.02 s2, 3details
#15ACCEPTED0.02 s2, 3details
#160.02 s2, 3details
#170.02 s2, 3details
#180.30 s3details
#190.49 s3details
#200.49 s3details
#21ACCEPTED0.49 s3details
#220.49 s3details
#230.50 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:51:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for (int i = 0; i < lists[1].size(); i++)
      |                             ~~^~~~~~~~~~~~~~~~~
input/code.cpp:58:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for (int i = 0; i < lists[2].size(); i++)
      |                             ~~^~~~~~~~~~~~~~~~~
input/code.cpp:82:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             for (int i = 0; i < lists[1].size(); i++)
      |                             ~~^~~~~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;
 
 
vector<int> v[202020];
int visited[202020];

vector<int> lists[3];

int findBottom(int i, int c, int list) {

    lists[list].push_back(i);
    visited[i] = true;

    
    if (v[i].size() > 2) {
        cout << "NO";
        exit(0);
    }
    for (int a : v[i]) {
        if (a == c) continue;
        return findBottom(a,i, list);
    }
    return i;
}
int main() {

    //ifstream in("input.txt");
    //cin.rdbuf(in.rdbuf());
    int n,m; cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a,b; cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    for (int i = 1; i <= n; i++)
    {
        if (v[i].size() == 3) {
            findBottom(v[i][0], i, 0);
            findBottom(v[i][1], i, 1);
            findBottom(v[i][2], i, 2);

            cout << "YES\n";
            cout << (lists[0].size() + lists[1].size() + 1);
            for (int i = lists[0].size()-1; i >= 0; i--) {
                cout << " " << lists[0][i];
            }
            cout << " " << i;
            for (int i = 0; i < lists[1].size(); i++)
            {
                cout << " " << lists[1][i];
            }
            cout << endl;

            cout << lists[2].size();
            for (int i = 0; i < lists[2].size(); i++)
            {
                cout << " " << lists[2][i];
            }

            exit(0);
        }
        else if (v[i].size() > 3) {
            cout << "NO\n";
            exit(0);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (v[i].size() == 2) {
            findBottom(v[i][0], i, 0);
            findBottom(v[i][1], i, 1);

            cout << "YES\n";
            cout << (lists[0].size() + lists[1].size());
            for (int i = lists[0].size()-1; i >= 0; i--) {
                cout << " " << lists[0][i];
            }
            cout << i << " ";
            for (int i = 0; i < lists[1].size(); i++)
            {
                cout << lists[1][i] << " ";
            }
            cout << "\n 0";
            exit(0);
        }
    }
    

    
}

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
2 0

correct output
YES
1 2 
1 1 

user output
(empty)

Test 2

Group: 1, 2, 3

Verdict:

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

correct output
YES
2 2 5 
3 1 3 4 

user output
NO

Test 3

Group: 1, 2, 3

Verdict:

input
200 300
74 145
156 176
192 168
141 133
...

correct output
YES
87 200 136 117 13 169 22 187 1...

user output
NO

Test 4

Group: 1, 2, 3

Verdict:

input
200 500
37 119
47 10
17 31
130 28
...

correct output
YES
90 84 70 170 117 129 17 31 186...

user output
NO

Test 5

Group: 1, 2, 3

Verdict:

input
200 500
79 1
104 127
31 38
83 85
...

correct output
YES
7 70 186 22 171 36 40 135 
193 41 91 25 42 160 83 2 173 5...

user output
NO

Test 6

Group: 1, 2, 3

Verdict:

input
200 500
145 50
4 102
136 55
148 34
...

correct output
YES
109 70 125 78 128 170 126 184 ...

user output
NO

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
200 500
44 38
198 85
69 167
74 39
...

correct output
NO

user output
NO

Test 8

Group: 1, 2, 3

Verdict:

input
200 500
41 93
98 4
171 72
127 166
...

correct output
YES
88 76 116 195 197 82 42 130 46...

user output
NO

Test 9

Group: 1, 2, 3

Verdict:

input
192 494
17 148
82 57
100 152
38 102
...

correct output
YES
154 191 183 77 3 173 83 112 15...

user output
NO

Test 10

Group: 1, 2, 3

Verdict:

input
193 497
24 110
17 193
129 117
23 186
...

correct output
YES
24 156 123 30 189 95 34 5 96 1...

user output
NO

Test 11

Group: 1, 2, 3

Verdict:

input
194 500
57 158
23 40
31 50
189 121
...

correct output
YES
27 168 116 136 175 180 12 89 6...

user output
NO

Test 12

Group: 2, 3

Verdict:

input
10000 15000
8243 3033
3299 579
4920 2342
2816 7811
...

correct output
YES
9236 3099 5585 9185 7222 9342 ...

user output
NO

Test 13

Group: 2, 3

Verdict:

input
10000 20000
6246 3603
5105 3531
6953 4682
2625 3510
...

correct output
YES
8734 5847 7473 5388 4872 4557 ...

user output
NO

Test 14

Group: 2, 3

Verdict:

input
10000 20000
5853 1019
2465 2936
2022 3609
9429 4118
...

correct output
YES
5204 3987 6388 4732 4403 7869 ...

user output
NO

Test 15

Group: 2, 3

Verdict: ACCEPTED

input
10000 20000
3439 3806
9336 5210
7784 848
5162 9830
...

correct output
NO

user output
NO

Test 16

Group: 2, 3

Verdict:

input
10000 20000
8908 287
2525 6024
1851 844
72 6898
...

correct output
YES
2487 3806 7839 4969 2661 4199 ...

user output
NO

Test 17

Group: 2, 3

Verdict:

input
7621 19995
6223 473
4893 990
5326 3614
421 591
...

correct output
YES
6340 5076 2779 1201 7053 1720 ...

user output
NO

Test 18

Group: 3

Verdict:

input
200000 300000
17151 175317
68698 43101
190738 54240
105443 37722
...

correct output
YES
163946 182154 120966 26194 771...

user output
NO

Test 19

Group: 3

Verdict:

input
200000 500000
128290 197429
67543 48696
156347 40114
114481 197
...

correct output
YES
30833 112330 10351 23335 11682...

user output
NO

Test 20

Group: 3

Verdict:

input
200000 500000
93623 55553
60858 72598
15531 30650
196624 28459
...

correct output
YES
99923 156477 12892 147937 1060...

user output
NO

Test 21

Group: 3

Verdict: ACCEPTED

input
200000 500000
76457 8199
163450 19462
107840 24269
178642 128924
...

correct output
NO

user output
NO

Test 22

Group: 3

Verdict:

input
200000 500000
181062 44502
115318 176115
33437 57568
163325 17752
...

correct output
YES
141551 129409 52010 108449 242...

user output
NO

Test 23

Group: 3

Verdict:

input
190479 499998
113031 136485
5993 50604
19834 84581
39043 93744
...

correct output
YES
170843 113031 163271 166394 43...

user output
NO