CSES - Siperia opettaa 4.0

CSES - Siperia opettaa 4.0 - Results

Submission details
Task:	Korn
Sender:	zxc
Submission time:	2016-08-04 15:59:28 +0300
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	100

Test results
test	verdict	time
#1	ACCEPTED	0.06 s	details
#2	ACCEPTED	0.06 s	details
#3	ACCEPTED	0.05 s	details
#4	ACCEPTED	0.06 s	details
#5	ACCEPTED	0.06 s	details
#6	ACCEPTED	0.06 s	details
#7	ACCEPTED	0.06 s	details
#8	ACCEPTED	0.06 s	details
#9	ACCEPTED	0.06 s	details
#10	ACCEPTED	0.06 s	details
#11	ACCEPTED	0.06 s	details
#12	ACCEPTED	0.07 s	details
#13	ACCEPTED	0.06 s	details
#14	ACCEPTED	0.06 s	details
#15	ACCEPTED	0.06 s	details
#16	ACCEPTED	0.06 s	details
#17	ACCEPTED	0.06 s	details
#18	ACCEPTED	0.06 s	details
#19	ACCEPTED	0.12 s	details
#20	ACCEPTED	0.09 s	details
#21	ACCEPTED	0.10 s	details
#22	ACCEPTED	0.19 s	details
#23	ACCEPTED	0.17 s	details
#24	ACCEPTED	0.20 s	details
#25	ACCEPTED	0.17 s	details
#26	ACCEPTED	0.18 s	details
#27	ACCEPTED	0.17 s	details
#28	ACCEPTED	0.17 s	details
#29	ACCEPTED	0.17 s	details
#30	ACCEPTED	0.17 s	details
#31	ACCEPTED	0.16 s	details
#32	ACCEPTED	0.18 s	details
#33	ACCEPTED	0.18 s	details
#34	ACCEPTED	0.17 s	details
#35	ACCEPTED	0.19 s	details
#36	ACCEPTED	0.22 s	details
#37	ACCEPTED	0.23 s	details
#38	ACCEPTED	0.20 s	details
#39	ACCEPTED	0.20 s	details
#40	ACCEPTED	0.06 s	details

Code

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int MN = 5e5+100;
vector<int> v[MN];
bool used[MN];
int f(int x, int ed, int lol) {
    used[x] = 1;
    for(int y: v[x]) {
        if(used[y] && y != ed && y != lol) {
            return 1;
        }
        if(!used[y]) {
            if(f(y, x, lol)) return 1;
        }
    }
    return 0;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    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);
    }
    int ma = 0;
    for(int i = 1; i <= n; ++i) {
        ma = max(ma, (int)v[i].size());
        if(v[i].size() % 2 != 0) {
            cout<<0<<endl;
            return 0;
        }
    }
    int maCnt = 0;
    for(int i = 1; i <= n; ++i) {
        if((int)v[i].size() == ma) ++maCnt;
    }
    if(maCnt > 2 && ma != 2) {
        cout<<0<<endl;
        return 0;
    }
    if(maCnt > 2 && ma == 2) {
        cout<<n<<endl;
        for(int i = 1; i <= n; ++i) {
            cout<<i<<' ';
        }
        cout<<endl;
        return 0;
    }
    //eli nyt maCnt <= 2
    vector<int> ans;
    for(int i = 1; i <= n; ++i) {
        if((int)v[i].size() == ma) {
            memset(used, 0, sizeof used);
            used[i] = 1;
            for(int x: v[i]) {
                if(!used[x] && f(x, i, i)) goto ohi;
            }
            ans.push_back(i);
            ohi:;
        }
    }
    cout<<ans.size()<<endl;
    for(int x: ans) {
        cout<<x<<' ';
    }
    cout<<'\n';
}

Test details

Test 1

Verdict: ACCEPTED

input
`6 8 3 5 5 1 3 4 4 1 ...` view save

correct output
`2 1 3` view save

user output
`2 1 3` view save

Test 2

Verdict: ACCEPTED

input
`3 3 1 2 2 3 3 1` view save

correct output
`3 1 2 3` view save

user output
`3 1 2 3` view save

Test 3

Verdict: ACCEPTED

input
`3 2 1 3 2 3` view save

correct output
`0` view save

user output
`0` view save

Test 4

Verdict: ACCEPTED

input
`5 7 1 3 4 2 1 2 1 4 ...` view save

correct output
`2 1 2` view save

user output
`2 1 2` view save

Test 5

Verdict: ACCEPTED

input
`5 5 5 3 1 5 2 1 4 2 ...` view save

correct output
`5 1 2 3 4 5` view save

user output
`5 1 2 3 4 5` view save

Test 6

Verdict: ACCEPTED

input
`5 6 4 1 5 3 1 5 4 3 ...` view save

correct output
`0` view save

user output
`0` view save

Test 7

Verdict: ACCEPTED

input
`10 14 2 3 5 2 4 3 6 3 ...` view save

correct output
`1 3` view save

user output
`1 3` view save

Test 8

Verdict: ACCEPTED

input
`10 10 4 5 2 9 8 1 7 10 ...` view save

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

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

Test 9

Verdict: ACCEPTED

input
`10 16 1 6 9 8 9 3 5 1 ...` view save

correct output
`2 1 9` view save

user output
`2 1 9` view save

Test 10

Verdict: ACCEPTED

input
`100 168 53 8 35 44 98 64 28 85 ...` view save

correct output
`1 62` view save

user output
`1 62` view save

Test 11

Verdict: ACCEPTED

input
`100 100 53 69 80 33 31 19 61 45 ...` view save

correct output
`100 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
`100 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

Test 12

Verdict: ACCEPTED

input
`100 196 44 85 68 86 86 55 44 56 ...` view save

correct output
`2 44 86` view save

user output
`2 44 86` view save

Test 13

Verdict: ACCEPTED

input
`1000 1636 85 954 434 807 657 942 363 998 ...` view save

correct output
`1 942` view save

user output
`1 942` view save

Test 14

Verdict: ACCEPTED

input
`1000 1000 154 824 455 878 521 429 806 795 ...` view save

correct output
`1000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
`1000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

Test 15

Verdict: ACCEPTED

input
`1000 1996 346 472 472 632 472 737 666 742 ...` view save

correct output
`2 472 666` view save

user output
`2 472 666` view save

Test 16

Verdict: ACCEPTED

input
`10000 16544 8723 5854 6694 5854 5813 9842 7775 450 ...` view save

correct output
`1 5854` view save

user output
`1 5854` view save

Test 17

Verdict: ACCEPTED

input
`10000 10000 6328 1933 3215 2119 133 597 5752 355 ...` view save

correct output
`10000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
`10000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

Test 18

Verdict: ACCEPTED

input
`10000 19996 3251 3276 7746 2914 7968 3276 4133 3276 ...` view save

correct output
`2 3276 7746` view save

user output
`2 3276 7746` view save

Test 19

Verdict: ACCEPTED

input
`100000 166466 48709 66850 19284 9360 70023 41035 10202 54726 ...` view save

correct output
`1 26348` view save

user output
`1 26348` view save

Test 20

Verdict: ACCEPTED

input
`100000 100000 13837 61303 89733 92564 27261 66328 53389 4963 ...` view save

correct output
`100000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

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

Test 21

Verdict: ACCEPTED

input
`100000 199996 7841 69346 92805 7841 2391 7841 35715 86148 ...` view save

correct output
`2 7841 86148` view save

user output
`2 7841 86148` view save

Test 22

Verdict: ACCEPTED

input
`200000 333292 177495 59529 65976 27906 183521 63384 130253 63384 ...` view save

correct output
`1 63384` view save

user output
`1 63384` view save

Test 23

Verdict: ACCEPTED

input
`200000 200000 172688 83121 94308 125397 121698 111684 122896 139134 ...` view save

correct output
`200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
`200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

Test 24

Verdict: ACCEPTED

input
`200000 399996 195502 195302 97487 195502 31836 180762 31836 114578 ...` view save

correct output
`2 31836 195502` view save

user output
`2 31836 195502` view save

Test 25

Verdict: ACCEPTED

input
`199999 299997 133842 56831 161198 197552 52013 56831 113824 141089 ...` view save

correct output
`1 56831` view save

user output
`1 56831` view save

Test 26

Verdict: ACCEPTED

input
`199966 266620 30805 74947 131498 74947 148055 45573 176247 144198 ...` view save

correct output
`1 74947` view save

user output
`1 74947` view save

Test 27

Verdict: ACCEPTED

input
`199996 239994 194088 176928 84078 66003 155399 181267 109363 24037 ...` view save

correct output
`1 109562` view save

user output
`1 109562` view save

Test 28

Verdict: ACCEPTED

input
`199991 219989 26995 182816 44231 104797 66799 189612 60325 120474 ...` view save

correct output
`1 104797` view save

user output
`1 104797` view save

Test 29

Verdict: ACCEPTED

input
`199901 201899 183049 162042 30129 98024 109542 162807 165887 186046 ...` view save

correct output
`1 174098` view save

user output
`1 174098` view save

Test 30

Verdict: ACCEPTED

input
`199001 199199 190576 15936 195289 88100 62330 151921 85433 28871 ...` view save

correct output
`1 193563` view save

user output
`1 193563` view save

Test 31

Verdict: ACCEPTED

input
`190001 190019 146460 136366 152584 71295 18424 74288 160666 4293 ...` view save

correct output
`1 27520` view save

user output
`1 27520` view save

Test 32

Verdict: ACCEPTED

input
`199999 200000 83463 54906 14939 155153 76174 149737 103606 118771 ...` view save

correct output
`1 72170` view save

user output
`1 72170` view save

Test 33

Verdict: ACCEPTED

input
`199999 250000 123656 75970 102071 118565 107227 44491 45664 44905 ...` view save

correct output
`1 123656` view save

user output
`1 123656` view save

Test 34

Verdict: ACCEPTED

input
`198999 232000 42059 44655 32973 54440 47844 127864 146216 69825 ...` view save

correct output
`1 54440` view save

user output
`1 54440` view save

Test 35

Verdict: ACCEPTED

input
`200000 343236 6172 121380 73997 136680 36608 38156 197529 31059 ...` view save

correct output
`0` view save

user output
`0` view save

Test 36

Verdict: ACCEPTED

input
`200000 449162 22188 74069 131951 149472 119926 72522 95032 63026 ...` view save

correct output
`0` view save

user output
`0` view save

Test 37

Verdict: ACCEPTED

input
`200000 449162 55595 43502 66495 49607 133565 22459 94162 167595 ...` view save

correct output
`0` view save

user output
`0` view save

Test 38

Verdict: ACCEPTED

input
`100000 425091 50386 81052 89464 80178 93037 61330 22465 60956 ...` view save

correct output
`0` view save

user output
`0` view save

Test 39

Verdict: ACCEPTED

input
`100000 474998 59563 73951 69846 82117 79750 49503 65426 15307 ...` view save

correct output
`0` view save

user output
`0` view save

Test 40

Verdict: ACCEPTED

input
`3 2 1 2 3 1` view save

correct output
`0` view save

user output
`0` view save

Siperia opettaa 4.0

Korn

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Tasks

Submissions (zxc)