Code Submission Evaluation System Login

NOI 2019 Open

Start:N/A
End:N/A
 

Tasks | Scoreboard | Statistics


CSES - NOI 2019 Open - Results
History
4:15:430
4:12:050
4:10:440
4:10:210
4:09:300
4:07:420
4:06:310
4:06:310
4:04:590
4:03:540
4:01:420
4:00:120
3:58:480
3:57:360
3:54:040
3:52:440
3:41:370
3:15:350
3:07:210
3:06:437
2:49:030
2:48:240
2:47:047
2:15:127
2:05:437
1:57:320
Task:Graph Ordering
Sender:eriksuenderhauf
Submission time:2019-03-07 19:11:49
Language:C++
Status:READY
Score:7

Feedback

groupverdictscore
#1ACCEPTED7
#2WRONG ANSWER0
#3WRONG ANSWER0
#4WRONG ANSWER0
#5WRONG ANSWER0

Test results

testverdicttime (s)group
#1ACCEPTED0.21 / 1.001, 4, 5details
#2ACCEPTED0.20 / 1.001, 5details
#3ACCEPTED0.13 / 1.001, 5details
#4ACCEPTED0.16 / 1.001, 5details
#5ACCEPTED0.17 / 1.001, 5details
#6ACCEPTED0.07 / 1.002, 3, 5details
#7WRONG ANSWER0.07 / 1.002, 3, 5details
#8WRONG ANSWER0.07 / 1.002, 3, 4, 5details
#9WRONG ANSWER0.07 / 1.002, 3, 4, 5details
#10WRONG ANSWER0.08 / 1.002, 3, 4, 5details
#11WRONG ANSWER0.06 / 1.002, 3, 5details
#12WRONG ANSWER0.07 / 1.002, 3, 5details
#13WRONG ANSWER0.07 / 1.002, 3, 4, 5details
#14WRONG ANSWER0.08 / 1.002, 3, 4, 5details
#15WRONG ANSWER0.07 / 1.002, 3, 4, 5details
#16WRONG ANSWER0.07 / 1.002, 3, 4, 5details
#17WRONG ANSWER0.07 / 1.002, 3, 4, 5details
#18WRONG ANSWER0.07 / 1.002, 3, 4, 5details
#19WRONG ANSWER0.06 / 1.003, 4, 5details
#20WRONG ANSWER0.06 / 1.003, 4, 5details
#21WRONG ANSWER0.07 / 1.003, 4, 5details
#22WRONG ANSWER0.06 / 1.003, 4, 5details
#23WRONG ANSWER0.07 / 1.003, 5details
#24WRONG ANSWER0.07 / 1.003, 5details
#25WRONG ANSWER0.07 / 1.003, 5details
#26WRONG ANSWER0.06 / 1.003, 5details
#27WRONG ANSWER0.07 / 1.003, 5details
#28WRONG ANSWER0.17 / 1.005details
#29WRONG ANSWER0.18 / 1.005details
#30WRONG ANSWER0.20 / 1.004, 5details
#31WRONG ANSWER0.20 / 1.004, 5details
#32WRONG ANSWER0.20 / 1.004, 5details
#33WRONG ANSWER0.21 / 1.004, 5details
#34WRONG ANSWER0.21 / 1.005details
#35WRONG ANSWER0.20 / 1.005details
#36WRONG ANSWER0.21 / 1.005details
#37ACCEPTED0.07 / 1.001, 2, 3, 4, 5details
#38ACCEPTED0.07 / 1.002, 3, 5details
#39ACCEPTED0.07 / 1.002, 3, 5details
#40ACCEPTED0.07 / 1.002, 3, 5details
#41ACCEPTED0.06 / 1.001, 2, 3, 5details
#42WRONG ANSWER0.07 / 1.002, 3, 5details
#43WRONG ANSWER0.07 / 1.003, 4, 5details
#44WRONG ANSWER0.08 / 1.003, 4, 5details
#45WRONG ANSWER0.08 / 1.002, 3, 4, 5details
#46WRONG ANSWER0.07 / 1.002, 3, 4, 5details
#47WRONG ANSWER0.07 / 1.002, 3, 5details
#48WRONG ANSWER0.07 / 1.003, 4, 5details
#49WRONG ANSWER0.07 / 1.004, 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:154: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:134: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);
    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();
            printf("%d ", x+1);
            vis[x] = 1;
            for (int y: adj[x]) {
                if (vis[y]) continue;
                vis[y] = 1;
                pq.pb(y);
            }
        }
        enl;
    }
    return 0;
}

Test details

Test 1

Group: 1, 4, 5

Verdict: ACCEPTED

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

correct output
1 44159 25721 84659 90058 9960...
view   save

user output
1 44159 25721 84659 90058 9960...
view   save

Test 2

Group: 1, 5

Verdict: ACCEPTED

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

correct output
68068 86325 91398 75677 51068 ...
view   save

user output
68068 86325 91398 75677 51068 ...
view   save

Test 3

Group: 1, 5

Verdict: ACCEPTED

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

correct output
IMPOSSIBLE

view   save

user output
IMPOSSIBLE

view   save

Test 4

Group: 1, 5

Verdict: ACCEPTED

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

correct output
IMPOSSIBLE

view   save

user output
IMPOSSIBLE

view   save

Test 5

Group: 1, 5

Verdict: ACCEPTED

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

correct output
IMPOSSIBLE

view   save

user output
IMPOSSIBLE

view   save

Test 6

Group: 2, 3, 5

Verdict: ACCEPTED

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

correct output
IMPOSSIBLE

view   save

user output
IMPOSSIBLE

view   save

Test 7

Group: 2, 3, 5

Verdict: WRONG ANSWER

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

correct output
IMPOSSIBLE

view   save

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

Test 8

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
1 32 2 49 83 64 29 26 10 87 58...
view   save

Test 9

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
12 64 81 74 97 49 16 2 23 47 5...
view   save

Test 10

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
1 12 7 56 17 21 39 2 41 59 27 ...
view   save

Test 11

Group: 2, 3, 5

Verdict: WRONG ANSWER

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

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

user output
IMPOSSIBLE

view   save

Test 12

Group: 2, 3, 5

Verdict: WRONG ANSWER

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

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

user output
69 77 37 53 51 90 1 13 20 21 8...
view   save

Test 13

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
IMPOSSIBLE

view   save

Test 14

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
IMPOSSIBLE

view   save

Test 15

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
20 73 34 26 52 6 29 19 70 5 

view   save

Test 16

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
IMPOSSIBLE

view   save

Test 17

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
47 12 10 58 24 2 22 4 29 

view   save

Test 18

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
10 31 2 21 59 48 8 1 

view   save

Test 19

Group: 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
270 853 953 188 880 3 934 546 ...
view   save

Test 20

Group: 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
1 951 164 151 205 797 4 654 14...
view   save

Test 21

Group: 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
1 176 761 788 860 676 217 17 6...
view   save

Test 22

Group: 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
1 46 499 244 60 903 156 606 47...
view   save

Test 23

Group: 3, 5

Verdict: WRONG ANSWER

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

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

user output
IMPOSSIBLE

view   save

Test 24

Group: 3, 5

Verdict: WRONG ANSWER

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

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

user output
915 684 422 881 319 359 87 456...
view   save

Test 25

Group: 3, 5

Verdict: WRONG ANSWER

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

correct output
IMPOSSIBLE

view   save

user output
943 12 525 434 680 168 413 770...
view   save

Test 26

Group: 3, 5

Verdict: WRONG ANSWER

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

correct output
IMPOSSIBLE

view   save

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

Test 27

Group: 3, 5

Verdict: WRONG ANSWER

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

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

user output
IMPOSSIBLE

view   save

Test 28

Group: 5

Verdict: WRONG ANSWER

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

correct output
45598 74078 1039 83702 16344 8...
view   save

user output
IMPOSSIBLE

view   save

Test 29

Group: 5

Verdict: WRONG ANSWER

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

correct output
79054 61855 53279 55546 60860 ...
view   save

user output
64977 541 86364 26734 99786 44...
view   save

Test 30

Group: 4, 5

Verdict: WRONG ANSWER

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

correct output
17857 81664 4369 61462 79754 8...
view   save

user output
1 47064 86745 17857 2116 4856 ...
view   save

Test 31

Group: 4, 5

Verdict: WRONG ANSWER

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

correct output
76869 5635 23236 12666 61633 8...
view   save

user output
1 73905 90654 76869 50785 7113...
view   save

Test 32

Group: 4, 5

Verdict: WRONG ANSWER

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

correct output
19788 11202 3496 24237 68564 5...
view   save

user output
1 18731 75042 87874 19788 7451...
view   save

Test 33

Group: 4, 5

Verdict: WRONG ANSWER

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

correct output
1 20339 9304 40427 67694 95656...
view   save

user output
1 82115 67687 38861 20339 3507...
view   save

Test 34

Group: 5

Verdict: WRONG ANSWER

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

correct output
IMPOSSIBLE

view   save

user output
69397 5 56227 40092 80496 3067...
view   save

Test 35

Group: 5

Verdict: WRONG ANSWER

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

correct output
IMPOSSIBLE

view   save

user output
44263 5 83267 56258 31220 6384...
view   save

Test 36

Group: 5

Verdict: WRONG ANSWER

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

correct output
IMPOSSIBLE

view   save

user output
37167 116 38170 92492 62963 86...
view   save

Test 37

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
2 1
2 1

view   save

correct output
1 2

view   save

user output
1 2 

view   save

Test 38

Group: 2, 3, 5

Verdict: ACCEPTED

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

correct output
IMPOSSIBLE

view   save

user output
IMPOSSIBLE

view   save

Test 39

Group: 2, 3, 5

Verdict: ACCEPTED

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

correct output
IMPOSSIBLE

view   save

user output
IMPOSSIBLE

view   save

Test 40

Group: 2, 3, 5

Verdict: ACCEPTED

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

correct output
4 2 3 1 5

view   save

user output
5 1 2 4 3 

view   save

Test 41

Group: 1, 2, 3, 5

Verdict: ACCEPTED

input
4 3
1 2
3 2
4 2

view   save

correct output
IMPOSSIBLE

view   save

user output
IMPOSSIBLE

view   save

Test 42

Group: 2, 3, 5

Verdict: WRONG ANSWER

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

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

user output
7 8 15 11 1 4 6 16 13 12 9 2 3...
view   save

Test 43

Group: 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
237 419 727 764 31 430 955 370...
view   save

Test 44

Group: 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
IMPOSSIBLE

view   save

Test 45

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
15 68 90 77 43 82 97 20 83 55 ...
view   save

Test 46

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
IMPOSSIBLE

view   save

Test 47

Group: 2, 3, 5

Verdict: WRONG ANSWER

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

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

user output
6 11 35 10 42 21 9 24 32 51 30...
view   save

Test 48

Group: 3, 4, 5

Verdict: WRONG ANSWER

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

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

user output
679 74 75 109 35 676 972 908 4...
view   save

Test 49

Group: 4, 5

Verdict: WRONG ANSWER

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

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

user output
4192 3562 6049 1489 2316 1843 ...
view   save