CSES - NOI 2019 Open - Results
Submission details
Task:Graph Ordering
Sender:return_my_2007
Submission time:2019-03-10 18:53:32 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#10.12 s1, 4, 5details
#20.12 s1, 5details
#30.09 s1, 5details
#40.11 s1, 5details
#50.11 s1, 5details
#60.02 s2, 3, 5details
#70.02 s2, 3, 5details
#80.02 s2, 3, 4, 5details
#90.02 s2, 3, 4, 5details
#100.01 s2, 3, 4, 5details
#110.02 s2, 3, 5details
#120.02 s2, 3, 5details
#130.02 s2, 3, 4, 5details
#140.02 s2, 3, 4, 5details
#150.01 s2, 3, 4, 5details
#160.03 s2, 3, 4, 5details
#170.01 s2, 3, 4, 5details
#180.02 s2, 3, 4, 5details
#190.02 s3, 4, 5details
#200.04 s3, 4, 5details
#210.02 s3, 4, 5details
#220.02 s3, 4, 5details
#230.02 s3, 5details
#240.03 s3, 5details
#250.03 s3, 5details
#260.02 s3, 5details
#270.02 s3, 5details
#280.15 s5details
#290.17 s5details
#300.16 s4, 5details
#310.14 s4, 5details
#320.16 s4, 5details
#330.17 s4, 5details
#340.16 s5details
#350.16 s5details
#360.17 s5details
#37ACCEPTED0.02 s1, 2, 3, 4, 5details
#380.02 s2, 3, 5details
#390.02 s2, 3, 5details
#400.02 s2, 3, 5details
#410.03 s1, 2, 3, 5details
#420.02 s2, 3, 5details
#430.02 s3, 4, 5details
#440.03 s3, 4, 5details
#450.02 s2, 3, 4, 5details
#460.02 s2, 3, 4, 5details
#470.02 s2, 3, 5details
#480.01 s3, 4, 5details
#490.04 s4, 5details

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int n, m;
vector <int> g[N];
bool used[N];
int pos[N];
void dfs(int u) {
    used[u] = 1;
    for (int v : g[u]) {
        if (pos[u] < pos[v] && !used[v]) dfs(v);
    }   
}   
void jfs(int u) {
    used[u] = 1;
    for (int v : g[u]) {
        if (pos[u] > pos[v] && !used[v]) jfs(v);
    }   
}   
void check(int u) {
    memset(used, 0, sizeof used);
    queue <int> q;
    q.push(u);
    used[u] = 1;
    vector <int> top;
    while (q.size()) {
        int u = q.front(); q.pop();
        top.push_back(u);
        for (int v : g[u]) {
            if (!used[v]) {
                q.push(v);
                used[v] = 1;
            }   
        }   
    }
    if ((int)top.size() < n) return;
    reverse(top.begin(), top.end());
    for (int f = 0; f < n; ++f) {
        if (f == u) continue;
        int p = -1;
        for (int i = 0; i < n; ++i) {
            if (top[i] == f) p = i;
        }   
        auto top1 = top;
        swap(top1[0], top1[p]);
        for (int i = 0; i < n; ++i) pos[top1[i]] = i;
        memset(used, 0, sizeof used);
        dfs(top1[0]);
        for (int i = 0; i < n; ++i) if (!used[i]) continue;
        memset(used, 0, sizeof used);
        jfs(top1.back());
        for (int i = 0; i < n; ++i) if (!used[i]) continue;
        for (int e : top1) cout << e + 1 << ' ';
        cout << '\n';
        exit(0);
    }
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v); g[v].push_back(u);
    }   
    for (int i = 0; i < n; ++i) {
        check(i);
    }   
    cout << "IMPOSSIBLE\n";
}   

Test details

Test 1

Group: 1, 4, 5

Verdict:

input
100000 99999
8326 74462
11810 58064
21677 73087
62986 25005
...

correct output
1 44159 25721 84659 90058 9960...

user output
2 55408 4224 23528 55621 26305...
Truncated

Test 2

Group: 1, 5

Verdict:

input
100000 99999
28990 31200
86271 56882
61089 18658
52422 57504
...

correct output
68068 86325 91398 75677 51068 ...

user output
2 37121 89333 44052 51784 8949...
Truncated

Test 3

Group: 1, 5

Verdict:

input
100000 99999
29378 80094
12282 29378
96138 29378
61870 29378
...

correct output
IMPOSSIBLE

user output
2 93795 90056 89911 74182 9571...
Truncated

Test 4

Group: 1, 5

Verdict:

input
100000 99999
97935 71091
9181 31715
73649 47675
45394 25464
...

correct output
IMPOSSIBLE

user output
2 64405 22461 22731 82060 8631...
Truncated

Test 5

Group: 1, 5

Verdict:

input
100000 99999
2897 55594
11759 89041
56061 8717
69672 73046
...

correct output
IMPOSSIBLE

user output
2 54142 87055 94984 15046 5359...
Truncated

Test 6

Group: 2, 3, 5

Verdict:

input
100 200
55 10
33 57
68 39
29 27
...

correct output
IMPOSSIBLE

user output
2 56 16 40 38 53 100 93 35 61 ...
Truncated

Test 7

Group: 2, 3, 5

Verdict:

input
100 175
71 86
100 88
83 92
25 73
...

correct output
IMPOSSIBLE

user output
2 46 63 84 38 64 8 20 53 68 91...
Truncated

Test 8

Group: 2, 3, 4, 5

Verdict:

input
100 200
26 58
49 25
66 20
20 85
...

correct output
1 2 86 60 34 92 23 4 44 89 76 ...

user output
2 23 44 72 30 21 28 38 50 36 4...
Truncated

Test 9

Group: 2, 3, 4, 5

Verdict:

input
100 195
19 28
63 48
1 57
1 20
...

correct output
12 97 18 74 36 10 78 50 61 95 ...

user output
2 24 54 96 90 100 71 32 5 7 59...
Truncated

Test 10

Group: 2, 3, 4, 5

Verdict:

input
100 193
48 66
15 67
32 14
36 78
...

correct output
1 56 13 32 14 49 75 93 18 6 54...

user output
2 38 23 82 93 4 46 53 29 71 28...
Truncated

Test 11

Group: 2, 3, 5

Verdict:

input
100 195
47 68
57 61
45 17
80 61
...

correct output
57 20 83 41 25 33 60 91 59 7 7...

user output
2 3 19 74 46 64 8 34 10 86 87 ...
Truncated

Test 12

Group: 2, 3, 5

Verdict:

input
100 185
43 78
76 99
78 39
83 61
...

correct output
78 43 32 88 26 28 64 81 7 72 2...

user output
2 52 92 40 23 65 74 14 9 63 70...
Truncated

Test 13

Group: 2, 3, 4, 5

Verdict:

input
99 132
96 16
18 89
98 50
66 26
...

correct output
1 12 45 71 97 22 35 9 60 27 20...

user output
2 5 54 99 56 8 81 62 51 88 93 ...
Truncated

Test 14

Group: 2, 3, 4, 5

Verdict:

input
98 144
25 6
30 34
58 25
31 41
...

correct output
32 7 92 1 63 86 87 14 90 17 81...

user output
2 43 98 72 22 71 51 94 89 84 6...
Truncated

Test 15

Group: 2, 3, 4, 5

Verdict:

input
96 145
19 70
72 92
27 72
17 85
...

correct output
1 50 30 4 10 48 42 5 70 19 29 ...

user output
2 81 16 95 96 80 74 36 90 57 7...
Truncated

Test 16

Group: 2, 3, 4, 5

Verdict:

input
96 158
79 74
41 70
8 5
73 90
...

correct output
7 59 44 27 1 30 49 28 80 52 15...

user output
2 53 96 55 32 76 86 13 93 60 5...
Truncated

Test 17

Group: 2, 3, 4, 5

Verdict:

input
96 142
95 35
67 89
91 70
48 21
...

correct output
13 20 81 33 1 51 19 69 16 85 6...

user output
2 61 93 83 54 28 65 41 46 30 7...
Truncated

Test 18

Group: 2, 3, 4, 5

Verdict:

input
72 111
70 17
25 3
58 24
52 9
...

correct output
21 59 48 8 1 2 31 10 11 41 4 5...

user output
2 38 6 29 72 55 28 3 12 25 66 ...
Truncated

Test 19

Group: 3, 4, 5

Verdict:

input
988 1563
402 701
830 801
50 578
8 144
...

correct output
1 136 368 683 447 304 131 53 8...

user output
2 201 132 99 535 988 154 519 5...
Truncated

Test 20

Group: 3, 4, 5

Verdict:

input
994 1555
171 541
66 915
330 350
494 251
...

correct output
1 164 205 151 951 797 4 654 14...

user output
2 678 408 373 994 519 156 196 ...
Truncated

Test 21

Group: 3, 4, 5

Verdict:

input
1000 2000
711 947
775 441
691 471
844 28
...

correct output
1 676 731 662 248 31 165 558 8...

user output
2 454 384 878 143 586 803 971 ...
Truncated

Test 22

Group: 3, 4, 5

Verdict:

input
1000 2000
811 889
873 984
83 52
144 511
...

correct output
60 909 522 568 40 77 181 441 8...

user output
2 757 534 375 134 39 381 135 2...
Truncated

Test 23

Group: 3, 5

Verdict:

input
1000 1869
625 715
448 714
110 927
432 1000
...

correct output
224 326 221 30 76 475 666 694 ...

user output
2 565 920 16 801 822 405 333 8...
Truncated

Test 24

Group: 3, 5

Verdict:

input
1000 1783
709 1
182 768
355 40
786 260
...

correct output
230 6 135 678 346 19 470 960 3...

user output
2 39 612 929 770 556 141 732 1...
Truncated

Test 25

Group: 3, 5

Verdict:

input
1000 2000
92 876
273 598
287 535
526 972
...

correct output
IMPOSSIBLE

user output
2 684 132 341 531 121 824 670 ...
Truncated

Test 26

Group: 3, 5

Verdict:

input
1000 1910
789 821
553 740
889 527
488 730
...

correct output
IMPOSSIBLE

user output
2 784 83 313 183 851 50 182 53...
Truncated

Test 27

Group: 3, 5

Verdict:

input
1000 1608
910 416
503 898
928 14
412 903
...

correct output
140 404 739 563 63 794 623 948...

user output
2 799 577 656 289 598 294 669 ...
Truncated

Test 28

Group: 5

Verdict:

input
100000 198666
5659 89691
91040 53375
96642 56177
28768 57001
...

correct output
45598 74078 1039 83702 16344 8...

user output
2 82655 88329 91125 89186 1769...
Truncated

Test 29

Group: 5

Verdict:

input
100000 197194
41636 91770
63018 23827
39207 93713
67765 47715
...

correct output
79054 61855 53279 55546 60860 ...

user output
2 67951 64209 7241 82707 39153...
Truncated

Test 30

Group: 4, 5

Verdict:

input
100000 199985
13674 42886
51349 6858
78502 18751
13628 65936
...

correct output
17857 81664 4369 61462 79754 8...

user output
2 32643 12872 41599 78599 9310...
Truncated

Test 31

Group: 4, 5

Verdict:

input
100000 200000
27666 33166
7161 81452
73134 30281
5106 29308
...

correct output
76869 5635 23236 12666 61633 8...

user output
2 32347 18323 88234 84119 3764...
Truncated

Test 32

Group: 4, 5

Verdict:

input
100000 200000
62814 54729
98407 26888
91808 70132
58916 49730
...

correct output
19788 11202 3496 24237 68564 5...

user output
2 52678 26686 92881 58870 4380...
Truncated

Test 33

Group: 4, 5

Verdict:

input
100000 200000
2299 91653
21125 75544
54029 94067
86513 45051
...

correct output
1 20339 9304 40427 67694 95656...

user output
2 93633 65861 65672 84180 1023...
Truncated

Test 34

Group: 5

Verdict:

input
100000 200000
34688 93668
78127 18902
55150 33116
273 88797
...

correct output
IMPOSSIBLE

user output
2 45288 23439 60233 75087 7585...
Truncated

Test 35

Group: 5

Verdict:

input
100000 200000
21026 14630
5605 59639
25604 78683
55713 70513
...

correct output
IMPOSSIBLE

user output
2 16075 23514 45510 59782 4757...
Truncated

Test 36

Group: 5

Verdict:

input
100000 200000
63190 73606
52072 54105
22092 31495
9189 37924
...

correct output
IMPOSSIBLE

user output
2 745 63207 13210 68675 70830 ...
Truncated

Test 37

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
2 1
2 1

correct output
1 2

user output
2 1 

Test 38

Group: 2, 3, 5

Verdict:

input
7 9
1 2
1 3
2 3
1 4
...

correct output
IMPOSSIBLE

user output
2 6 5 4 3 7 1 

Test 39

Group: 2, 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
2 8 6 5 7 4 3 9 1 

Test 40

Group: 2, 3, 5

Verdict:

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

correct output
4 2 3 1 5

user output
2 5 3 4 1 

Test 41

Group: 1, 2, 3, 5

Verdict:

input
4 3
1 2
3 2
4 2

correct output
IMPOSSIBLE

user output
2 3 4 1 

Test 42

Group: 2, 3, 5

Verdict:

input
17 30
4 1
3 14
6 16
13 6
...

correct output
7 8 11 15 1 2 9 3 14 13 5 10 1...

user output
2 14 9 5 10 13 16 11 8 12 3 17...

Test 43

Group: 3, 4, 5

Verdict:

input
992 1712
377 709
847 640
261 902
761 693
...

correct output
870 1 925 928 950 257 766 520 ...

user output
2 887 33 372 992 699 595 397 3...
Truncated

Test 44

Group: 3, 4, 5

Verdict:

input
990 1672
305 445
800 155
365 779
824 247
...

correct output
108 461 160 696 895 655 376 21...

user output
2 990 589 194 783 692 812 258 ...
Truncated

Test 45

Group: 2, 3, 4, 5

Verdict:

input
99 169
35 32
97 43
22 62
33 7
...

correct output
19 70 62 22 54 78 25 14 3 81 1...

user output
2 93 80 89 95 67 16 85 12 58 1...
Truncated

Test 46

Group: 2, 3, 4, 5

Verdict:

input
99 164
62 73
19 35
55 92
79 91
...

correct output
21 25 64 90 17 15 89 95 70 33 ...

user output
2 99 39 52 80 48 58 31 18 51 6...
Truncated

Test 47

Group: 2, 3, 5

Verdict:

input
53 68
7 46
51 14
3 18
8 40
...

correct output
32 30 38 33 27 12 8 20 2 34 45...

user output
2 6 39 35 3 41 10 18 16 40 42 ...
Truncated

Test 48

Group: 3, 4, 5

Verdict:

input
996 1902
661 201
19 613
895 438
180 32
...

correct output
220 795 198 239 40 164 773 834...

user output
2 330 693 103 252 288 490 996 ...
Truncated

Test 49

Group: 4, 5

Verdict:

input
6110 11528
3366 4718
3226 2188
5022 1186
3205 5349
...

correct output
1 2527 2211 554 4201 4522 1494...

user output
2 843 4082 3522 5199 5047 5557...
Truncated