CSES - NOI 2019 Open - Results
Submission details
Task:Graph Ordering
Sender:eriksuenderhauf
Submission time:2019-03-07 19:20:41
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#10.07 s1, 4, 5details
#20.07 s1, 5details
#30.06 s1, 5details
#40.07 s1, 5details
#50.06 s1, 5details
#60.09 s2, 3, 5details
#70.08 s2, 3, 5details
#80.07 s2, 3, 4, 5details
#90.08 s2, 3, 4, 5details
#100.07 s2, 3, 4, 5details
#110.07 s2, 3, 5details
#120.06 s2, 3, 5details
#130.06 s2, 3, 4, 5details
#140.07 s2, 3, 4, 5details
#150.07 s2, 3, 4, 5details
#160.07 s2, 3, 4, 5details
#170.07 s2, 3, 4, 5details
#180.07 s2, 3, 4, 5details
#190.07 s3, 4, 5details
#200.07 s3, 4, 5details
#210.12 s3, 4, 5details
#220.45 s3, 4, 5details
#230.07 s3, 5details
#240.07 s3, 5details
#250.13 s3, 5details
#260.07 s3, 5details
#270.07 s3, 5details
#280.06 s5details
#290.06 s5details
#300.06 s4, 5details
#310.06 s4, 5details
#320.06 s4, 5details
#330.07 s4, 5details
#340.06 s5details
#350.07 s5details
#360.07 s5details
#370.06 s1, 2, 3, 4, 5details
#380.06 s2, 3, 5details
#390.07 s2, 3, 5details
#400.06 s2, 3, 5details
#410.07 s1, 2, 3, 5details
#420.07 s2, 3, 5details
#430.07 s3, 4, 5details
#440.07 s3, 4, 5details
#450.08 s2, 3, 4, 5details
#460.08 s2, 3, 4, 5details
#470.07 s2, 3, 5details
#480.07 s3, 4, 5details
#490.06 s4, 5details

Compiler report

input/code.cpp: In function 'void solve(int)':
input/code.cpp:65:9: warning: unused variable 'c' [-Wunused-variable]
     int c = 0, c2 = 0, c3 = ++cnt;
         ^
input/code.cpp:65:16: warning: unused variable 'c2' [-Wunused-variable]
     int c = 0, c2 = 0, c3 = ++cnt;
                ^~
input/code.cpp: In function 'int main()':
input/code.cpp:155:23: warning: unused variable 'pre' [-Wunused-variable]
         int ind = -1, pre = -1;
                       ^~~
input/code.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
input/code.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

Code

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
int low[MAXN], disc[MAXN];
int vis[MAXN], t = 1, ap[MAXN];
vi adj[MAXN];
vector<vi> comps;
deque<int> st;

void dfs(int u, int p) {
    vis[u] = 1;
    disc[u] = low[u] = t++;
    int children = 0;
    st.pb(u);
    for (int v: adj[u]) {
        if (!vis[v]) {
            children++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if ((p != -1 && disc[u] <= low[v]) || (p == -1 && children > 1)) {
                ap[u] = 1;
            }
        } else if (v != p) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

vi comp[MAXN], adj2[MAXN];
int cnt = 0;

void solve(int u) {
    vis[u] = 1;
    int c = 0, c2 = 0, c3 = ++cnt;
    comp[c3].pb(u);
    for (int v: adj[u]) {
        if (vis[v]) continue;
        if (ap[v]) {
            adj2[c3].pb(cnt+1);
            adj2[cnt+1].pb(c3);
            solve(v);
            continue;
        }
        vi nx;
        deque<int> pq;
        pq.push_back(v);
        int cur = ++cnt;
        adj2[c3].pb(cur);
        adj2[cur].pb(c3);
        while (!pq.empty()) {
            int x = pq.front(); pq.pop_front();
            vis[x] = 1;
            comp[cur].pb(x);
            for (int y: adj[x]) {
                if (vis[y]) continue;
                vis[y] = 1;
                if (ap[y]) {
                    nx.pb(y);
                    continue;
                }
                pq.pb(y);
            }
        }
        for (int k: nx) {
            if (vis[k]) continue;
            adj2[cur].pb(cnt+1);
            adj2[cnt+1].pb(cur);
            solve(k);
        }
    }
}

vi ans;
int i2[MAXN];

void dfs2(int u, int p) {
    for (int v: comp[u]) {
        ans.pb(v);
        i2[v] = ans.size()-1;
    }
    for (int v: adj2[u])
        if (v != p)
            dfs2(v, u);
}

int findP(int x, int y, int i) {
    if (x == y) return 1;
    for (int v: adj[x]) {
        if (i2[v] > i2[x]) {
            int r = findP(v, y, i);
            if (r == 1) return 1;
        }
    }
    return 0;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    if (n > 2000) return -1;
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        u--, v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(0, -1);
    memset(vis, 0, sizeof vis);
    bool fl = false;
    for (int i = 0; i < n; i++) {
        if (ap[i]) {
            solve(i);
            fl = true;
            break;
        }
    }
    /*for (int i = 1; i <= cnt; i++, enl)
        for (int j: comp[i])
            printf("%d ", j);*/
        pri(cnt);
    if (fl) {
        int ind = -1, pre = -1;
        for (int i = 1; i <= cnt; i++)
            if (adj2[i].size() == 1)
                ind = i;
            else if (adj2[i].size() > 2)
                return !printf("IMPOSSIBLE\n");
        dfs2(ind, -1);
        for (int i: ans) {
            int ret = findP(ans[0], i, i);
            if (ret == 0)
                return -1;
        }
        for (int i: ans)
            printf("%d ", i+1);
        enl;
    } else {
        deque<int> pq;
        pq.pb(0);
        while (!pq.empty()) {
            int x = pq.front(); pq.pop_front();
            ans.pb(x);
            i2[x] = ans.size()-1;
            vis[x] = 1;
            for (int y: adj[x]) {
                if (vis[y]) continue;
                vis[y] = 1;
                pq.pb(y);
            }
        }
        for (int i: ans) {
            int ret = findP(ans[0], i, i);
            if (ret == 0)
                return -1;
        }
        for (int i: ans)
            printf("%d ", i+1);
        enl;
    }
    return 0;
}

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
(empty)

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
(empty)

Test 3

Group: 1, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
(empty)

Test 4

Group: 1, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
(empty)

Test 5

Group: 1, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
(empty)

Test 6

Group: 2, 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
7
IMPOSSIBLE

Test 7

Group: 2, 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
3
95 16 28 91 8 64 83 89 6 68 46...

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
0
1 32 2 49 83 64 29 26 10 87 58...

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
3
12 64 81 74 97 49 16 2 23 47 5...

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
0
1 12 7 56 17 21 39 2 41 59 27 ...

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
5
IMPOSSIBLE

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
4
69 77 37 53 51 90 1 13 20 21 8...

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
19
IMPOSSIBLE

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
19
IMPOSSIBLE

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
4
20 73 34 26 52 6 29 19 70 5 

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
13
IMPOSSIBLE

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
6
47 12 10 58 24 2 22 4 29 

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
4
10 31 2 21 59 48 8 1 

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
6
270 853 953 188 880 3 934 546 ...

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
4
1 951 164 151 205 797 4 654 14...

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
0
1 176 761 788 860 676 217 17 6...

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
0
1 46 499 244 60 903 156 606 47...

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
5
IMPOSSIBLE

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
3
915 684 422 881 319 359 87 456...

Test 25

Group: 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
3
943 12 525 434 680 168 413 770...

Test 26

Group: 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
3
83 35 81 745 243 413 360 395 9...

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
7
IMPOSSIBLE

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

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
(empty)

Test 34

Group: 5

Verdict:

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

correct output
IMPOSSIBLE

user output
(empty)

Test 35

Group: 5

Verdict:

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

correct output
IMPOSSIBLE

user output
(empty)

Test 36

Group: 5

Verdict:

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

correct output
IMPOSSIBLE

user output
(empty)

Test 37

Group: 1, 2, 3, 4, 5

Verdict:

input
2 1
2 1

correct output
1 2

user output
0
1 2 

Test 38

Group: 2, 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
4
IMPOSSIBLE

Test 39

Group: 2, 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
6
IMPOSSIBLE

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
3
5 1 2 4 3 

Test 41

Group: 1, 2, 3, 5

Verdict:

input
4 3
1 2
3 2
4 2

correct output
IMPOSSIBLE

user output
4
IMPOSSIBLE

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
3
7 8 15 11 1 4 6 16 13 12 9 2 3...

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
4
237 419 727 764 31 430 955 370...

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
9
IMPOSSIBLE

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
4
15 68 90 77 43 82 97 20 83 55 ...

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
7
IMPOSSIBLE

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
8
6 11 35 10 42 21 9 24 32 51 30...

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
3
679 74 75 109 35 676 972 908 4...

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
(empty)