CSES - NOI 2019 Open

CSES - NOI 2019 Open - Results

Submission details
Task:	Graph Ordering
Sender:	wakaka
Submission time:	2019-03-16 08:16:41 +0200
Language:	C++
Status:	READY
Result:	28

Feedback
group	verdict	score
#1	ACCEPTED	7
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0
#4	ACCEPTED	21
#5	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.40 s	1, 4, 5	details
#2	ACCEPTED	0.41 s	1, 5	details
#3	ACCEPTED	0.27 s	1, 5	details
#4	ACCEPTED	0.33 s	1, 5	details
#5	ACCEPTED	0.36 s	1, 5	details
#6	ACCEPTED	0.03 s	2, 3, 5	details
#7	ACCEPTED	0.03 s	2, 3, 5	details
#8	ACCEPTED	0.04 s	2, 3, 4, 5	details
#9	ACCEPTED	0.04 s	2, 3, 4, 5	details
#10	ACCEPTED	0.03 s	2, 3, 4, 5	details
#11	ACCEPTED	0.04 s	2, 3, 5	details
#12	ACCEPTED	0.03 s	2, 3, 5	details
#13	ACCEPTED	0.03 s	2, 3, 4, 5	details
#14	ACCEPTED	0.03 s	2, 3, 4, 5	details
#15	ACCEPTED	0.04 s	2, 3, 4, 5	details
#16	ACCEPTED	0.04 s	2, 3, 4, 5	details
#17	ACCEPTED	0.03 s	2, 3, 4, 5	details
#18	ACCEPTED	0.04 s	2, 3, 4, 5	details
#19	ACCEPTED	0.02 s	3, 4, 5	details
#20	ACCEPTED	0.03 s	3, 4, 5	details
#21	ACCEPTED	0.05 s	3, 4, 5	details
#22	ACCEPTED	0.03 s	3, 4, 5	details
#23	ACCEPTED	0.04 s	3, 5	details
#24	ACCEPTED	0.03 s	3, 5	details
#25	ACCEPTED	0.03 s	3, 5	details
#26	ACCEPTED	0.04 s	3, 5	details
#27	ACCEPTED	0.03 s	3, 5	details
#28	ACCEPTED	0.67 s	5	details
#29	ACCEPTED	0.69 s	5	details
#30	ACCEPTED	0.64 s	4, 5	details
#31	ACCEPTED	0.63 s	4, 5	details
#32	ACCEPTED	0.66 s	4, 5	details
#33	ACCEPTED	0.65 s	4, 5	details
#34	ACCEPTED	0.63 s	5	details
#35	ACCEPTED	0.63 s	5	details
#36	ACCEPTED	0.63 s	5	details
#37	ACCEPTED	0.03 s	1, 2, 3, 4, 5	details
#38	ACCEPTED	0.03 s	2, 3, 5	details
#39	WRONG ANSWER	0.03 s	2, 3, 5	details
#40	ACCEPTED	0.02 s	2, 3, 5	details
#41	ACCEPTED	0.03 s	1, 2, 3, 5	details
#42	ACCEPTED	0.03 s	2, 3, 5	details
#43	ACCEPTED	0.03 s	3, 4, 5	details
#44	ACCEPTED	0.03 s	3, 4, 5	details
#45	ACCEPTED	0.03 s	2, 3, 4, 5	details
#46	ACCEPTED	0.04 s	2, 3, 4, 5	details
#47	ACCEPTED	0.03 s	2, 3, 5	details
#48	ACCEPTED	0.03 s	3, 4, 5	details
#49	ACCEPTED	0.06 s	4, 5	details

Compiler report

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

Code

#include <bits/stdc++.h>
using namespace std;
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
typedef long long ll;
typedef long double ld;
const int MAXN = 100005;
const int MAXM = 200005;
vector<int> E[MAXN];
pair<int, int> edges[MAXM];
namespace blockcut {
vector<int> preorder;
int low[MAXN]; // topmost vertex a descendent can reach via back-edge
int H[MAXN];
bool cut[MAXN]; // cut[x] -> x is a cut vertex
int parent[MAXN];
vector<int> blocke[MAXN]; // all edges in a block
vector<int> blockv[MAXN]; // all vertices in a block
// a tree-edge is rep by the deeper vertex. a block is rep by highest tree edge.
int vblock[MAXN]; // block of the parent-edge (vblock[1] = 0, vblock[blockId] = blockId)
int eblock[MAXM]; // block of edge
vector<int> adjBlock[MAXN]; // cut nodes adjacent to a block
vector<int> adjCut[MAXN]; // blocks adjacent to a cut node, empty means not cut
void go(int x) {
	preorder.push_back(x);
	low[x] = x;
	int totch = 0;
	for (auto y : E[x]) {
		if (H[y] == -1) {
			H[y] = H[x] + 1;
			parent[y] = x;
			++totch;
			go(y);
			if (H[low[y]] < H[low[x]]) low[x] = low[y];
			if (H[low[y]] >= H[x] && x != 1) cut[x] = true;
		} else if (H[y] < H[x] - 1) {
			// This is a backedge that is not to the parent
			if (H[y] < H[low[x]]) low[x] = y;
		}
	}
	if (x == 1 && totch > 1) cut[x] = true;
}
void getBlocks(int n, int m) {
	memset(H, -1, sizeof(H));
	H[1] = 0;
	go(1);
	for (int x : preorder) {
		if (!parent[x]) continue;
		if (H[low[x]] < H[parent[x]]) vblock[x] = vblock[parent[x]];
		else vblock[x] = x;
	}
	for (int i = 0; i < m; ++i) {
		auto e = edges[i];
		int deeper = H[e.first] > H[e.second] ? e.first : e.second;
		eblock[i] = vblock[deeper];
	}
	for (int i = 0; i < m; ++i) {
		blocke[eblock[i]].push_back(i);
		blockv[eblock[i]].push_back(edges[i].first);
		blockv[eblock[i]].push_back(edges[i].second);
	}
	// If we need the block-cut tree; this takes n log n
	for (int i = 1; i <= n; ++i) {
		sort(blockv[i].begin(), blockv[i].end());
		blockv[i].erase(unique(blockv[i].begin(), blockv[i].end()), blockv[i].end());
		for (int x : blockv[i]) {
			if (cut[x]) {
				adjCut[x].push_back(i);
				adjBlock[i].push_back(x);
			}
		}
	}
}
};
namespace bipolar {
int H[MAXN];
int low[MAXN];
void dfs(int x) {
	low[x] = x;
	for (auto y : E[x]) {
		if (H[y] == -1) {
			H[y] = H[x] + 1;
			dfs(y);
			if (H[low[y]] < H[low[x]]) low[x] = low[y];
		} else if (H[y] < H[x] - 1) {
			// This is a backedge that is not to the parent
			if (H[y] < H[low[x]]) low[x] = y;
		}
	}
}
bool vis[MAXN];
bool isBefore[MAXN];
list<int> ordering;
list<int>::iterator vpos[MAXN];
void dfsOrder(int x, int p = -1) {
	vis[x] = true;
	if (low[x] != x) { // low[x] == x should only occur for vertex s
		if (isBefore[low[x]]) {
			vpos[x] = ordering.insert(vpos[p], x);
		} else {
			vpos[x] = ordering.insert(next(vpos[p]), x);
		}
		// Update isBefore for relation (parent[x], x)
		isBefore[p] = !isBefore[low[x]];
	}
	for (auto y : E[x])
		if (!vis[y]) dfsOrder(y, x);
}
// NOTE: this modifies edges array E!
void getOrdering(int n, int s, int t) {
	if (n == 2) {
		ordering = {1, 2};
		return;
	}
	memset(H, -1, sizeof(H));
	H[s] = 0;
	// Make sure t is first neighbor of s
	E[s].insert(E[s].begin(), t);
	E[t].push_back(s);
	dfs(s);
	isBefore[s] = false;
	vpos[s] = ordering.insert(ordering.end(), s);
	dfsOrder(s);
}
};
using namespace blockcut;
using namespace bipolar;
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	map<pair<int, int>, int> mp;
	for (int i = 0; i < m; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
		edges[i] = {a, b};
		mp[{a, b}] = mp[{b, a}] = i;
	}
	getBlocks(n, m);
	int s = -1, t = -1;
	// Every cut node has <= two neighboring blocks.
	for (int i = 1; i <= n; ++i) {
		if (adjCut[i].size() > 2) {
			printf("IMPOSSIBLE\n");
			return 0;
		}
	}
	// Get two blocks adjacent to only 1 cut node
	for (int i = 1; i <= n; ++i) {
		if (adjBlock[i].size() == 1) {
			assert(blockv[i].size() >= 2);
			int x = cut[blockv[i][0]] ? blockv[i][1] : blockv[i][0];
			if (s == -1) s = x;
			else t = x;
		}
	}
	if (s == -1) {
		s = 1;
		t = 2;
	}
	getOrdering(n, s, t);
	for (int x : ordering) printf("%d ", x);
}

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

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

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: ACCEPTED

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

correct output
`IMPOSSIBLE` view save

user output
`IMPOSSIBLE` view save

Test 8

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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 29 18 69 14 5 57 19 8 63 21 ...` Truncated

Test 9

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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
`5 71 24 54 96 39 32 100 90 60 ...` Truncated

Test 10

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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 56 13 32 80 14 22 49 75 93 1...` Truncated

Test 11

Group: 2, 3, 5

Verdict: ACCEPTED

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
`1 50 70 17 51 18 62 44 48 15 5...` Truncated

Test 12

Group: 2, 3, 5

Verdict: ACCEPTED

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
`23 40 52 59 92 65 74 14 80 70 ...` Truncated

Test 13

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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
`1 12 45 71 97 22 35 9 60 27 20...` Truncated

Test 14

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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

Test 15

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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

Test 16

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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
`32 37 96 53 55 76 86 60 93 51 ...` Truncated

Test 17

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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

Test 18

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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
`1 8 48 59 21 2 31 10 11 41 4 5...` Truncated

Test 19

Group: 3, 4, 5

Verdict: ACCEPTED

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
`1 136 368 683 447 304 131 53 8...` Truncated

Test 20

Group: 3, 4, 5

Verdict: ACCEPTED

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
`327 994 678 373 408 519 156 19...` Truncated

Test 21

Group: 3, 4, 5

Verdict: ACCEPTED

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 676 731 248 31 662 788 207 6...` Truncated

Test 22

Group: 3, 4, 5

Verdict: ACCEPTED

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 651 903 478 67 600 60 909...` Truncated

Test 23

Group: 3, 5

Verdict: ACCEPTED

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
`224 326 221 30 76 475 666 694 ...` Truncated

Test 24

Group: 3, 5

Verdict: ACCEPTED

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
`6 19 346 678 135 230 470 960 3...` Truncated

Test 25

Group: 3, 5

Verdict: ACCEPTED

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

correct output
`IMPOSSIBLE` view save

user output
`IMPOSSIBLE` view save

Test 26

Group: 3, 5

Verdict: ACCEPTED

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

correct output
`IMPOSSIBLE` view save

user output
`IMPOSSIBLE` view save

Test 27

Group: 3, 5

Verdict: ACCEPTED

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
`63 794 563 739 404 140 623 948...` Truncated

Test 28

Group: 5

Verdict: ACCEPTED

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
`90 74884 75317 98010 69831 717...` Truncated

Test 29

Group: 5

Verdict: ACCEPTED

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

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

user output
`1721 7241 18523 86069 96207 52...` Truncated

Test 30

Group: 4, 5

Verdict: ACCEPTED

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 44643 17857 73639 8166...` Truncated

Test 31

Group: 4, 5

Verdict: ACCEPTED

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 50785 14730 66904 9004...` Truncated

Test 32

Group: 4, 5

Verdict: ACCEPTED

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 87874 11202 3496 24237 33785...` Truncated

Test 33

Group: 4, 5

Verdict: ACCEPTED

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 67687 2467 66521 2098 1694 5...` Truncated

Test 34

Group: 5

Verdict: ACCEPTED

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

correct output
`IMPOSSIBLE` view save

user output
`IMPOSSIBLE` view save

Test 35

Group: 5

Verdict: ACCEPTED

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

correct output
`IMPOSSIBLE` view save

user output
`IMPOSSIBLE` view save

Test 36

Group: 5

Verdict: ACCEPTED

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

correct output
`IMPOSSIBLE` view save

user output
`IMPOSSIBLE` 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: WRONG ANSWER

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

correct output
`IMPOSSIBLE` view save

user output
`2 3 1 4 6 5 7 9 8` 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
`2 4 3 1 5` 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: ACCEPTED

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

Test 43

Group: 3, 4, 5

Verdict: ACCEPTED

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
`1 870 925 928 90 552 366 826 6...` Truncated

Test 44

Group: 3, 4, 5

Verdict: ACCEPTED

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
`1 326 88 160 461 213 376 655 8...` Truncated

Test 45

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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
`1 19 70 62 22 3 81 17 54 78 25...` Truncated

Test 46

Group: 2, 3, 4, 5

Verdict: ACCEPTED

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
`1 75 38 96 42 16 33 70 95 89 1...` Truncated

Test 47

Group: 2, 3, 5

Verdict: ACCEPTED

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 49 5 37 ...` Truncated

Test 48

Group: 3, 4, 5

Verdict: ACCEPTED

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
`17 490 252 996 693 330 77 288 ...` Truncated

Test 49

Group: 4, 5

Verdict: ACCEPTED

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
`433 5664 1304 3522 5541 4274 4...` Truncated

NOI 2019 Open

Graph Ordering

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Tasks

Submissions (wakaka)