CSES - NOI 2019 Open - Results
Submission details
Task:Graph Ordering
Sender:tmk
Submission time:2019-03-10 13:41:15
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.12 s1, 4, 5details
#20.11 s1, 5details
#30.16 s1, 5details
#40.12 s1, 5details
#50.11 s1, 5details
#60.02 s2, 3, 5details
#70.02 s2, 3, 5details
#8ACCEPTED0.03 s2, 3, 4, 5details
#90.02 s2, 3, 4, 5details
#10ACCEPTED0.02 s2, 3, 4, 5details
#110.02 s2, 3, 5details
#120.02 s2, 3, 5details
#130.01 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.03 s3, 4, 5details
#210.02 s3, 4, 5details
#220.02 s3, 4, 5details
#230.03 s3, 5details
#240.02 s3, 5details
#250.02 s3, 5details
#260.01 s3, 5details
#270.02 s3, 5details
#280.18 s5details
#290.20 s5details
#300.23 s4, 5details
#310.21 s4, 5details
#320.20 s4, 5details
#330.20 s4, 5details
#340.23 s5details
#350.24 s5details
#360.23 s5details
#37ACCEPTED0.02 s1, 2, 3, 4, 5details
#380.03 s2, 3, 5details
#390.02 s2, 3, 5details
#400.02 s2, 3, 5details
#410.01 s1, 2, 3, 5details
#420.02 s2, 3, 5details
#430.01 s3, 4, 5details
#440.02 s3, 4, 5details
#450.01 s2, 3, 4, 5details
#460.02 s2, 3, 4, 5details
#470.02 s2, 3, 5details
#480.03 s3, 4, 5details
#490.04 s4, 5details

Code

#include<bits/stdc++.h>
using namespace std;
#ifndef d
#define d(...)
#endif
#define st first
#define nd second
#define pb push_back
#define siz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
typedef long long LL;
typedef long double LD;
constexpr int INF=1e9+7;
constexpr LL INFL=1e18;
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

constexpr int maxn = 100005, maxm = 200005;

int n, m, deg[maxn];
vector<int> G[maxn];
bool vis[maxn];


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i=0; i<m; i++) {
		int a, b;
		cin >> a >> b;
		G[a].pb(b);
		G[b].pb(a);
		deg[a]++, deg[b]++;
	}
	
	queue<int> q;
	q.push(1);
	
	set<int> touched; 
	touched.insert(1);
	
	while(not q.empty() or not touched.empty()) {
		while(not q.empty()) {
			auto w = q.front(); q.pop();
			if(vis[w]) continue;
			vis[w] = true;
			cout << w << " ";
			touched.erase(w);
			for(auto v:G[w]) {
				if(not vis[v]) {
					touched.insert(v);
					if(--deg[v] <= 1)
						q.push(v);
				}
			}
		}
		
		if(not touched.empty()) {
			auto w = *touched.begin();
			touched.erase(touched.begin());
			q.push(w);
		}
	}
	
	cout << "\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...

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 79070 41248 35589 31979 1799...

Test 3

Group: 1, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 29378 80094 12282 96138 6187...

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 55546 5971...

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 2880...

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 31 32 36 41 29 7 9 53 22 ...

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 12 86 3 13 9 14 76 8...

Test 8

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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 64 2 8 63 9 16 19 20 66 85 1...

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 30 13 20 67 23 25 6 41 17...

Test 10

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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 59 12 2 17 13 56 16 21 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 85 22 89 50 54 26 39 27 61 5...

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 95 79 5 98 84 13 21 86 18 20...

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

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 92 7 32 63 86 14 87 90 17 81...

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 30 4 10 48 42 5 70 19 29 ...

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 30 7 49 44 59 28 80 52 15...

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 13 33 81 51 19 6 85 69 16...

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

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

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 205 151 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
1 176 17 623 42 103 122 931 66...

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 651 60 156 244 54 153 668...

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 424 736 586 137 179 375 ...

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 179 485 364 253 44 3...

Test 25

Group: 3, 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 111 315 118 435 148 136 146 ...

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 616 274 147 206 862 ...

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 762 17 100 361 359 782 394 9...

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 15400 59741 12748 3796...

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 14528 49480 43665 513 5...

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 44643 2116 4856 2192 1...

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 50785 14730 13045 2868...

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 68179 47411 40474 3390...

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 1996 3320 4806 66825 6...

Test 34

Group: 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 4404 19492 12627 40166 17197...

Test 35

Group: 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 45742 46089 3485 45419 6754 ...

Test 36

Group: 5

Verdict:

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

correct output
IMPOSSIBLE

user output
1 78892 6246 6553 10210 18536 ...

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 5 6 7 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 5 4 

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

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 46 743 14 233 184 204 402 33...

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 108 696 730 160 461 8...

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 70 41 56 66 34 14 25 78 5...

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 81 21 10 29 25 36 37 4...

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 50 37 5 49 24 9 21 42 10 ...

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 40 239 164 384 31 232 56...

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 5118 2168 1958 2211 554...