CSES - NOI 2019 Open - Results
Submission details
Task:Graph Ordering
Sender:koosaga
Submission time:2019-03-10 06:48:16 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.13 s1, 4, 5details
#20.13 s1, 5details
#30.10 s1, 5details
#40.13 s1, 5details
#50.13 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.03 s2, 3, 4, 5details
#110.03 s2, 3, 5details
#120.03 s2, 3, 5details
#130.02 s2, 3, 4, 5details
#140.02 s2, 3, 4, 5details
#150.02 s2, 3, 4, 5details
#160.02 s2, 3, 4, 5details
#170.02 s2, 3, 4, 5details
#180.02 s2, 3, 4, 5details
#190.02 s3, 4, 5details
#200.02 s3, 4, 5details
#210.03 s3, 4, 5details
#220.03 s3, 4, 5details
#230.03 s3, 5details
#240.03 s3, 5details
#250.02 s3, 5details
#260.01 s3, 5details
#270.03 s3, 5details
#280.18 s5details
#290.17 s5details
#300.19 s4, 5details
#310.18 s4, 5details
#320.18 s4, 5details
#330.18 s4, 5details
#340.20 s5details
#350.19 s5details
#360.19 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.01 s2, 3, 5details
#430.02 s3, 4, 5details
#440.02 s3, 4, 5details
#450.02 s2, 3, 4, 5details
#460.02 s2, 3, 4, 5details
#470.01 s2, 3, 5details
#480.02 s3, 4, 5details
#490.04 s4, 5details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:52:7: 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:54:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, e; scanf("%d %d",&s,&e);
             ~~~~~^~~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<lint, int> pi;
const int MAXN = 100005;

vector<int> gph[MAXN];
int dfn[MAXN], low[MAXN], cut[MAXN], piv;

void dfs(int x, int p){
	dfn[x] = low[x] = ++piv;
	int cnt = 0;
	for(auto &i : gph[x]){
		if(i != p){
			if(!dfn[i]){
				dfs(i, x);
				low[x] = min(low[x], low[i]);
				if(low[i] > dfn[x]) cnt++;
			}
			else low[x] = min(low[x], dfn[i]);
		}
	}
	if(p == -1) cnt--;
	if(cnt > 0) cut[x] = 1;
}

lint dist[MAXN];
void solve(int s, int t){
	priority_queue<pi, vector<pi>, greater<pi> > pq;
	memset(dist, 0x3f, sizeof(dist));
	vector<int> ord;
	pq.emplace(0, s);
	dist[s] = 0;
	cut[t] = 1e9;
	while(!pq.empty()){
		auto x = pq.top(); pq.pop();
		if(dist[x.second] != x.first) continue;
		ord.push_back(x.second);
		for(auto &i : gph[x.second]){
			lint nxtcost = x.first + cut[i] * 1e9 + 1;
			if(dist[i] > nxtcost){
				dist[i] = nxtcost;
				pq.emplace(dist[i], i);
			}
		}
	}
	for(auto &i : ord) printf("%d ", i);
}

int main(){
	int n, m;
	scanf("%d %d",&n,&m);
	for(int i=0; i<m; i++){
		int s, e; scanf("%d %d",&s,&e);
		gph[s].push_back(e);
		gph[e].push_back(s);
	}
	dfs(1, -1);
	solve(1, n);
}

Test details

Test 1

Group: 1, 4, 5

Verdict: ACCEPTED

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

correct output
1 44159 25721 84659 90058 9960...

user output
1 44159 25721 84659 90058 9960...
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
1 41248 79070 31979 35589 1799...
Truncated

Test 3

Group: 1, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 29378 2 3 4 5 6 7 8 9 10 11 ...
Truncated

Test 4

Group: 1, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 80554 19212 23650 95964 8598...
Truncated

Test 5

Group: 1, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 84452 91138 32516 43863 1289...
Truncated

Test 6

Group: 2, 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 37 52 58 73 84 3 10 11 12 15...
Truncated

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 5 14 48 94 2 12 13 21 ...
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
1 2 29 32 49 64 83 3 8 9 10 18...
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
1 11 13 20 23 57 88 18 19 25 3...
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
1 7 12 56 2 13 17 21 27 30 39 ...
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
1 22 50 73 85 6 26 54 58 61 70...
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
1 5 13 18 42 55 62 79 84 87 90...
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
1 12 45 71 97 22 35 9 60 27 20...
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
1 7 32 92 63 86 14 87 90 17 81...
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
1 50 4 30 10 48 42 5 70 19 29 ...
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
1 27 44 59 7 30 49 28 52 80 15...
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
1 20 33 81 13 51 19 6 69 85 16...
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
1 8 48 59 21 2 31 10 11 41 4 5...
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
1 136 368 683 447 304 131 53 8...
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
1 151 164 205 951 797 4 654 14...
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
1 176 676 761 788 860 17 135 1...
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
1 46 244 499 54 60 143 156 175...
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
1 456 736 854 114 137 143 413 ...
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
1 320 416 523 709 25 174 179 2...
Truncated

Test 25

Group: 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 111 595 739 795 77 118 145 1...
Truncated

Test 26

Group: 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 123 159 274 147 341 452 616 ...
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
1 17 100 394 618 762 814 301 3...
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
1 14297 59741 79735 12748 1540...
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
1 4670 70693 14528 25107 49480...
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
1 47064 86745 2116 4856 16377 ...
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
1 73905 90654 441 2281 3256 41...
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
1 18731 75042 87874 11202 1355...
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
1 20339 38861 67687 82115 1996...
Truncated

Test 34

Group: 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 4404 19492 72325 95150 97832...
Truncated

Test 35

Group: 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 45742 46089 69880 74575 7858...
Truncated

Test 36

Group: 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 6246 70600 77471 78892 6553 ...
Truncated

Test 37

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
2 1
2 1

correct output
1 2

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

Test 39

Group: 2, 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 2 3 4 7 5 6 8 9 

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

Test 41

Group: 1, 2, 3, 5

Verdict:

input
4 3
1 2
3 2
4 2

correct output
IMPOSSIBLE

user output
1 2 3 4 

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

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 914 925 862 928 90 274 9...
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
1 326 88 213 108 160 376 655 8...
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
1 19 41 70 56 62 22 28 34 3 14...
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
1 75 38 96 42 64 10 16 25 33 9...
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
1 28 51 13 14 32 38 50 15 17 2...
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
1 220 384 929 31 40 80 232 637...
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
1 2527 4533 1607 2211 2610 373...
Truncated