CSES - NOI 2019 Open - Results
Submission details
Task:Graph Ordering
Sender:eriksuenderhauf
Submission time:2019-03-07 20:02:42
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#10.09 s1, 4, 5details
#20.07 s1, 5details
#30.09 s1, 5details
#40.08 s1, 5details
#50.08 s1, 5details
#60.10 s2, 3, 5details
#70.11 s2, 3, 5details
#80.10 s2, 3, 4, 5details
#90.10 s2, 3, 4, 5details
#100.11 s2, 3, 4, 5details
#110.10 s2, 3, 5details
#120.10 s2, 3, 5details
#130.10 s2, 3, 4, 5details
#140.10 s2, 3, 4, 5details
#150.10 s2, 3, 4, 5details
#160.11 s2, 3, 4, 5details
#170.10 s2, 3, 4, 5details
#180.10 s2, 3, 4, 5details
#190.35 s3, 4, 5details
#200.36 s3, 4, 5details
#210.38 s3, 4, 5details
#220.38 s3, 4, 5details
#230.35 s3, 5details
#240.38 s3, 5details
#250.38 s3, 5details
#260.33 s3, 5details
#270.35 s3, 5details
#280.08 s5details
#290.07 s5details
#300.07 s4, 5details
#310.08 s4, 5details
#320.08 s4, 5details
#330.08 s4, 5details
#340.07 s5details
#350.08 s5details
#360.07 s5details
#370.08 s1, 2, 3, 4, 5details
#380.08 s2, 3, 5details
#390.09 s2, 3, 5details
#400.09 s2, 3, 5details
#410.08 s1, 2, 3, 5details
#420.08 s2, 3, 5details
#430.37 s3, 4, 5details
#440.34 s3, 4, 5details
#450.10 s2, 3, 4, 5details
#460.11 s2, 3, 4, 5details
#470.10 s2, 3, 5details
#480.37 s3, 4, 5details
#490.08 s4, 5details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:103: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:107: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 vis[MAXN], ap[MAXN], rev[MAXN];
vi adj[MAXN];

void dfs(int u) {
    vis[u] = 1;
    for (int v: adj[u])
        if (!vis[v])
            dfs(v);
}
vi comp[MAXN], adj2[MAXN];
vi sol[MAXN];

void dfs2(int u, int c) {
    vis[u] = c;
    rev[u] = c;
    comp[c].pb(u);
    for (int v: adj[u])
        if (!vis[v] && !ap[v])
            dfs2(v, c);
}

vi ans;
int i2[MAXN];

void dfs3(int u, int p, int st) {
    int nx = st;
    if (comp[u].size() != 1) {
        deque<int> pq;
        pq.push_back(st);
        while (!pq.empty()) {
            int x = pq.front(); pq.pop_front();
            vis[x] = 1;
            ans.pb(x);
            i2[x] = ans.size()-1;
            for (int y: adj[x]) {
                if (rev[y] != rev[x]) continue;
                if (vis[y] == 1) continue;
                vis[y] = 1;
                pq.push_back(y);
            }
        }
    } else {
        //printf("%d ", comp[u][0]+1);
        ans.pb(comp[u][0]);
        i2[comp[u][0]] = ans.size()-1;
        for (int v: adj[comp[u][0]])
            if (!vis[v])
                nx = v;
    }
    for (int v: adj2[u])
        if (v != p)
            dfs3(v, u, nx);
}

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);
    }
    for (int i = 0; i < n; i++) {
        memset(vis, 0, sizeof vis);
        vis[i] = 1;
        int cnt = 0;
        for (int v: adj[i])
            if (!vis[v])
                dfs(v), cnt++;
        if (cnt > 1) ap[i] = 1;
        //if (cnt > 2) return !printf("IMPOSSIBLE\n");
        //if (cnt == 2) ap[i] = 1;
    }
    memset(vis, 0, sizeof vis);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (ap[i]) {
            vis[i] = ++cnt;
            rev[i] = cnt;
            comp[cnt].pb(i);
            continue;
        }
        if (vis[i] != 0) continue;
        dfs2(i, ++cnt);
    }
    for (int i = 0; i < n; i++) {
        for (int v: adj[i]) {
            if (rev[i] != rev[v]) continue;
            adj2[rev[i]].pb(rev[v]);
            adj2[rev[v]].pb(rev[i]);
        }
    }
    for (int i = 1; i <= cnt; i++) {
        sort(adj2[i].begin(), adj2[i].end());
        adj2[i].erase(unique(adj2[i].begin(), adj2[i].end()), adj2[i].end());
        if (adj2[i].size() > 2) return !printf("IMPOSSIBLE\n");
    }
    /*memset(vis, 0, sizeof vis);
    for (int i = 0; i < n; i++) {
        if (ap[i] != 1) continue;
        vis[i] = 1;
    }
    for (int i = 0; i < n; i++) {
        if (ap[i] != 1) continue;
        for (int x: adj[i]) {
            if (vis[x]) continue;
            deque<int> pq;
            pq.push_back(x);
            while (!pq.empty()) {

            }
        }
    }*/
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= cnt; i++) {
        if (adj2[i].size() == 1) {
            dfs3(i, -1, comp[i][0]);
            break;
        }
    }
    for (int i: ans) printf("%d ", i + 1);
    enl;
    for (int i: ans) {
        int ret = findP(ans[0], i, i);
        if (ret == 0)
            return -1;
    }
    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
1 58 73 84 52 37 60 76 15 66 2...

Test 7

Group: 2, 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 17 42 48 5 94 14 96 66 2 26 ...

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
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
1 57 20 11 23 13 88 53 99 56 4...

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
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
1 50 22 73 85 26 54 70 81 89 6...

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 56 76 49 3 99 83 38 29 10 30...

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
3 68 87 3 

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
1 7 32 92 1 

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 46 61 2 

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
1 59 27 44 7 1 

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
1 33 20 81 13 1 

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
1 8 48 59 21 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
2 189 2 

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
1 951 164 151 205 797 1 

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
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
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
1 736 456 586 424 1 

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
1 416 523 320 485 179 364 696 ...

Test 25

Group: 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 739 595 111 795 77 707 514 9...

Test 26

Group: 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 274 123 159 147 452 892 867 ...

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
5 627 210 356 24 5 

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

Test 39

Group: 2, 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
2 3 2 

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

Test 41

Group: 1, 2, 3, 5

Verdict:

input
4 3
1 2
3 2
4 2

correct output
IMPOSSIBLE

user output
(empty)

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 5 9 16 10 12 17 3 6 14 13 4 ...

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
1 870 925 914 928 862 90 950 2...

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
1 326 88 213 160 655 895 108 3...

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
1 19 41 70 56 62 34 22 28 14 7...

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
1 75 96 38 64 42 10 25 90 95 1...

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
1 51 28 14 13 38 32 50 17 25 5...

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
1 929 384 220 873 795 80 834 3...

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)