CSES - Siperia opettaa 5.0

Submission details
Task:	HDRF
Sender:	mangolassi
Submission time:	2017-03-09 16:56:46 +0200
Language:	C++
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time
#1	ACCEPTED	0.05 s	details
#2	TIME LIMIT EXCEEDED	--	details
#3	TIME LIMIT EXCEEDED	--	details
#4	TIME LIMIT EXCEEDED	--	details
#5	TIME LIMIT EXCEEDED	--	details
#6	TIME LIMIT EXCEEDED	--	details
#7	TIME LIMIT EXCEEDED	--	details
#8	TIME LIMIT EXCEEDED	--	details
#9	ACCEPTED	0.05 s	details
#10	TIME LIMIT EXCEEDED	--	details
#11	TIME LIMIT EXCEEDED	--	details
#12	TIME LIMIT EXCEEDED	--	details
#13	TIME LIMIT EXCEEDED	--	details
#14	TIME LIMIT EXCEEDED	--	details
#15	TIME LIMIT EXCEEDED	--	details
#16	TIME LIMIT EXCEEDED	--	details
#17	TIME LIMIT EXCEEDED	--	details
#18	TIME LIMIT EXCEEDED	--	details
#19	TIME LIMIT EXCEEDED	--	details
#20	TIME LIMIT EXCEEDED	--	details
#21	TIME LIMIT EXCEEDED	--	details
#22	TIME LIMIT EXCEEDED	--	details
#23	TIME LIMIT EXCEEDED	--	details
#24	TIME LIMIT EXCEEDED	--	details
#25	TIME LIMIT EXCEEDED	--	details
#26	TIME LIMIT EXCEEDED	--	details
#27	TIME LIMIT EXCEEDED	--	details
#28	TIME LIMIT EXCEEDED	--	details
#29	TIME LIMIT EXCEEDED	--	details
#30	TIME LIMIT EXCEEDED	--	details
#31	TIME LIMIT EXCEEDED	--	details
#32	TIME LIMIT EXCEEDED	--	details
#33	TIME LIMIT EXCEEDED	--	details
#34	TIME LIMIT EXCEEDED	--	details
#35	TIME LIMIT EXCEEDED	--	details
#36	TIME LIMIT EXCEEDED	--	details
#37	TIME LIMIT EXCEEDED	--	details
#38	TIME LIMIT EXCEEDED	--	details
#39	TIME LIMIT EXCEEDED	--	details
#40	TIME LIMIT EXCEEDED	--	details
#41	TIME LIMIT EXCEEDED	--	details
#42	TIME LIMIT EXCEEDED	--	details
#43	TIME LIMIT EXCEEDED	--	details
#44	TIME LIMIT EXCEEDED	--	details
#45	TIME LIMIT EXCEEDED	--	details
#46	TIME LIMIT EXCEEDED	--	details
#47	TIME LIMIT EXCEEDED	--	details
#48	TIME LIMIT EXCEEDED	--	details
#49	TIME LIMIT EXCEEDED	--	details
#50	TIME LIMIT EXCEEDED	--	details
#51	TIME LIMIT EXCEEDED	--	details
#52	TIME LIMIT EXCEEDED	--	details
#53	TIME LIMIT EXCEEDED	--	details
#54	TIME LIMIT EXCEEDED	--	details
#55	TIME LIMIT EXCEEDED	--	details
#56	TIME LIMIT EXCEEDED	--	details
#57	TIME LIMIT EXCEEDED	--	details
#58	TIME LIMIT EXCEEDED	--	details
#59	TIME LIMIT EXCEEDED	--	details
#60	TIME LIMIT EXCEEDED	--	details
#61	TIME LIMIT EXCEEDED	--	details
#62	TIME LIMIT EXCEEDED	--	details
#63	ACCEPTED	0.55 s	details

Compiler report

input/code.cpp: In function 'void make(int, int&)':
input/code.cpp:39:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int k = 0; k < kids[i].size(); ++k) {
                                   ^
input/code.cpp: In function 'void make_cover(int, int)':
input/code.cpp:99:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int k = 0; k < kids[i].size(); ++k) {
                                   ^
input/code.cpp: In function 'int main()':
input/code.cpp:138:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nums.size(); ++i) {
                                ^

Code

#include <iostream>
#include <vector>
#include <algorithm>
const int inf = 1e9 + 7;
const int N = 1e5 + 1;
const int M = 9;
std::vector<int> kids[N];
int par[N];
int cover[N][M];
int pri[N];
int depth[N];

// For LCA
int pos[N];
int segment[8 * N];
int h;

int get(int ls, int le, int i = 1, int s = 0, int e = h) {
	if (le < s || e < ls) return inf;
	if (ls <= s && e <= le) return segment[i];
	int mid = (s + e) / 2;
	int res = std::min(get(ls, le, 2 * i, s, mid), get(ls, le, 2 * i + 1, mid+1, e));
	return res;
}

void set(int i, int s, int e, int ind, int v) {
	if (ind < s || e < ind) return;
	if (s == e) { segment[i] = v; return; }
	int mid = (s + e) / 2;
	set(2 * i, s, mid, ind, v);
	set(2 * i + 1, mid+1, e, ind, v);
	segment[i] = std::min(segment[2 * i], segment[2 * i + 1]);	
}

void make(int i, int& s) {
	pos[i] = s;
	set(1, 0, h, s, depth[i]);
	++s;
	for (int k = 0; k < kids[i].size(); ++k) {
		make(kids[i][k], s);
		set(1, 0, h, s, depth[i]);
		++s;
	}
}
// End for LCA

struct Odd {
	int ind;

	bool operator< (const Odd& oth) const {
		int ap = pos[ind];
		int bp = pos[oth.ind];
		int lca = (ap < bp ? get(ap, bp) : get(bp, ap));
		if (depth[ind] == lca) {
			return false;
		} else if (depth[oth.ind] == lca) {
			return true;
		}
		int ai = ind;
		int k = 1;
		while(k > 0) {
			while((depth[cover[ai][k]] > lca) && (k < M)) {
				++k;
			}
			--k;
			ai = cover[ai][k];
		}
		k = 1;
		int bi = oth.ind;
		while(k > 0) {
			while((depth[cover[bi][k]] > lca) && (k < M)) {
				++k;
			}
			--k;
			bi = cover[bi][k];
		}
		return pri[ai] < pri[bi];
	}
};

int up(int val, int a, int k) {
	while((k >= 0) && (pri[cover[a][k]] < val)) {
		--k;
	}
	if (k >= 1) {
		return up(val, cover[a][k], k);
	} else {
		return cover[a][k+1];
	}
}

void make_cover(int i = 1, int d = 1) {
	depth[i] = d;
	cover[i][0] = i;
	cover[i][1] = up(pri[i], par[i], M-1);
	for (int j = 2; j < M-1; ++j) {
		cover[i][j] = cover[cover[i][j-1]][j-1];
	}
	for (int k = 0; k < kids[i].size(); ++k) {
		make_cover(kids[i][k], d + 1);
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	
	int n;
	std::cin >> n;
	
	par[1] = 0;
	for (int i = 2; i <= n; ++i) {
		std::cin >> par[i];
		kids[par[i]].push_back(i);
	}
	for (int i = 1; i <= n; ++i) {
		std::cin >> pri[i];
	}
	cover[1][0] = 1;
	depth[0] = 0;
	make_cover();
	h = 2 * n;
	int tmp = 1;
	while(tmp <= h) {
		tmp <<= 1;
	}
	h = tmp;
	--h;
	tmp = 0;	
	make(1, tmp);	
	std::vector<Odd> nums;
	for (int i = 1; i <= n; ++i) {
		Odd d;
		d.ind = i;
		nums.push_back(d);
	}
	std::sort(nums.begin(), nums.end());
	for (int i = 0; i < nums.size(); ++i) {
		std::cout << nums[i].ind << " ";
	}
	std::cout << "\n";
}

Test details

Test 1

Verdict: ACCEPTED

input
`2 1 1 2` view save

correct output
`2 1` view save

user output
`2 1` view save

Test 2

Verdict: TIME LIMIT EXCEEDED

input
`100 85 42 34 7 48 48 63 90 37 80 2...` view save

correct output
`95 2 85 65 59 8 36 24 82 71 61...` view save

user output
(empty)

Test 3

Verdict: TIME LIMIT EXCEEDED

input
`100 14 35 99 80 25 28 11 70 24 51 ...` view save

correct output
`72 77 43 9 93 49 70 13 69 66 7...` view save

user output
(empty)

Test 4

Verdict: TIME LIMIT EXCEEDED

input
`100 60 55 18 87 58 26 35 17 48 9 8...` view save

correct output
`89 77 39 93 49 64 56 38 74 80 ...` view save

user output
(empty)

Test 5

Verdict: TIME LIMIT EXCEEDED

input
`100 57 68 23 81 85 54 62 73 100 10...` view save

correct output
`10 11 100 40 58 86 67 28 26 51...` view save

user output
(empty)

Test 6

Verdict: TIME LIMIT EXCEEDED

input
`100 33 22 18 33 26 31 57 23 93 97 ...` view save

correct output
`60 100 4 10 76 50 71 94 17 20 ...` view save

user output
(empty)

Test 7

Verdict: TIME LIMIT EXCEEDED

input
`200 87 30 52 56 164 149 193 82 188...` view save

correct output
`191 178 85 36 55 35 43 3 30 97...` view save

user output
(empty)

Test 8

Verdict: TIME LIMIT EXCEEDED

input
`200 3 59 148 66 188 81 172 152 170...` view save

correct output
`115 121 107 74 151 91 80 118 2...` view save

user output
(empty)

Test 9

Verdict: ACCEPTED

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

correct output
`3 2 4 5 1` view save

user output
`3 2 4 5 1` view save

Test 10

Verdict: TIME LIMIT EXCEEDED

input
`200 158 82 152 26 46 191 100 180 2...` view save

correct output
`13 181 18 163 24 130 2 158 184...` view save

user output
(empty)

Test 11

Verdict: TIME LIMIT EXCEEDED

input
`200 197 134 27 109 102 77 30 71 14...` view save

correct output
`112 144 12 131 64 137 175 117 ...` view save

user output
(empty)

Test 12

Verdict: TIME LIMIT EXCEEDED

input
`200 101 78 128 55 9 78 35 87 56 6 ...` view save

correct output
`197 138 177 126 68 147 145 73 ...` view save

user output
(empty)

Test 13

Verdict: TIME LIMIT EXCEEDED

input
`300 259 151 284 164 193 153 20 153...` view save

correct output
`63 240 115 257 206 66 42 113 2...` view save

user output
(empty)

Test 14

Verdict: TIME LIMIT EXCEEDED

input
`300 127 280 20 1 186 215 59 101 25...` view save

correct output
`10 257 179 56 174 135 42 169 2...` view save

user output
(empty)

Test 15

Verdict: TIME LIMIT EXCEEDED

input
`300 81 283 149 69 227 39 144 70 28...` view save

correct output
`207 54 241 126 151 138 118 51 ...` view save

user output
(empty)

Test 16

Verdict: TIME LIMIT EXCEEDED

input
`300 12 265 12 226 196 226 179 185 ...` view save

correct output
`220 198 242 11 256 125 212 174...` view save

user output
(empty)

Test 17

Verdict: TIME LIMIT EXCEEDED

input
`300 91 60 106 191 300 27 191 10 28...` view save

correct output
`247 142 103 178 256 9 154 16 8...` view save

user output
(empty)

Test 18

Verdict: TIME LIMIT EXCEEDED

input
`400 331 329 307 121 72 279 344 213...` view save

correct output
`346 367 343 332 11 100 44 77 1...` view save

user output
(empty)

Test 19

Verdict: TIME LIMIT EXCEEDED

input
`400 305 158 217 151 291 189 338 26...` view save

correct output
`114 319 34 163 183 13 175 87 3...` view save

user output
(empty)

Test 20

Verdict: TIME LIMIT EXCEEDED

input
`400 354 21 151 275 188 159 154 328...` view save

correct output
`232 184 314 111 112 227 393 5 ...` view save

user output
(empty)

Test 21

Verdict: TIME LIMIT EXCEEDED

input
`400 279 376 349 253 29 112 157 110...` view save

correct output
`131 226 382 240 276 66 136 190...` view save

user output
(empty)

Test 22

Verdict: TIME LIMIT EXCEEDED

input
`400 370 349 95 374 373 220 187 223...` view save

correct output
`269 29 129 266 222 394 395 275...` view save

user output
(empty)

Test 23

Verdict: TIME LIMIT EXCEEDED

input
`500 55 153 455 345 272 93 24 440 4...` view save

correct output
`69 104 10 499 433 251 337 470 ...` view save

user output
(empty)

Test 24

Verdict: TIME LIMIT EXCEEDED

input
`500 297 2 308 68 421 288 151 117 3...` view save

correct output
`494 444 419 370 107 261 439 16...` view save

user output
(empty)

Test 25

Verdict: TIME LIMIT EXCEEDED

input
`500 448 452 207 81 168 458 431 499...` view save

correct output
`445 117 188 206 156 438 321 13...` view save

user output
(empty)

Test 26

Verdict: TIME LIMIT EXCEEDED

input
`500 462 261 399 462 328 277 22 319...` view save

correct output
`73 258 171 245 148 181 110 297...` view save

user output
(empty)

Test 27

Verdict: TIME LIMIT EXCEEDED

input
`500 344 249 220 264 277 322 90 164...` view save

correct output
`36 419 257 318 414 355 179 107...` view save

user output
(empty)

Test 28

Verdict: TIME LIMIT EXCEEDED

input
`600 518 98 32 91 331 69 562 488 31...` view save

correct output
`438 286 235 368 340 354 338 39...` view save

user output
(empty)

Test 29

Verdict: TIME LIMIT EXCEEDED

input
`600 107 462 245 156 410 126 414 28...` view save

correct output
`116 194 344 560 59 337 543 233...` view save

user output
(empty)

Test 30

Verdict: TIME LIMIT EXCEEDED

input
`600 158 283 486 462 491 341 528 83...` view save

correct output
`581 301 19 557 374 433 396 278...` view save

user output
(empty)

Test 31

Verdict: TIME LIMIT EXCEEDED

input
`600 222 353 470 77 426 573 201 36 ...` view save

correct output
`346 194 423 385 43 161 373 154...` view save

user output
(empty)

Test 32

Verdict: TIME LIMIT EXCEEDED

input
`600 563 593 20 438 30 525 291 199 ...` view save

correct output
`275 171 292 426 133 136 285 21...` view save

user output
(empty)

Test 33

Verdict: TIME LIMIT EXCEEDED

input
`700 578 320 44 92 179 368 524 61 5...` view save

correct output
`127 21 504 411 619 214 103 230...` view save

user output
(empty)

Test 34

Verdict: TIME LIMIT EXCEEDED

input
`700 172 367 171 680 68 431 90 465 ...` view save

correct output
`336 263 10 104 370 572 544 173...` view save

user output
(empty)

Test 35

Verdict: TIME LIMIT EXCEEDED

input
`700 592 485 633 263 13 500 234 164...` view save

correct output
`580 329 635 17 574 191 672 280...` view save

user output
(empty)

Test 36

Verdict: TIME LIMIT EXCEEDED

input
`700 281 479 279 98 11 309 125 538 ...` view save

correct output
`509 340 171 226 298 317 16 200...` view save

user output
(empty)

Test 37

Verdict: TIME LIMIT EXCEEDED

input
`700 129 142 226 50 471 445 533 580...` view save

correct output
`69 96 324 645 208 167 652 431 ...` view save

user output
(empty)

Test 38

Verdict: TIME LIMIT EXCEEDED

input
`800 299 797 180 295 481 278 317 59...` view save

correct output
`149 251 709 708 421 733 798 24...` view save

user output
(empty)

Test 39

Verdict: TIME LIMIT EXCEEDED

input
`800 61 61 439 356 175 216 137 325 ...` view save

correct output
`792 30 44 426 502 39 390 264 3...` view save

user output
(empty)

Test 40

Verdict: TIME LIMIT EXCEEDED

input
`800 310 772 726 621 51 556 795 711...` view save

correct output
`318 161 733 86 72 271 483 670 ...` view save

user output
(empty)

Test 41

Verdict: TIME LIMIT EXCEEDED

input
`800 24 46 39 770 278 218 657 362 7...` view save

correct output
`566 303 132 186 47 504 78 356 ...` view save

user output
(empty)

Test 42

Verdict: TIME LIMIT EXCEEDED

input
`800 166 688 171 741 50 312 299 562...` view save

correct output
`119 186 291 331 48 603 575 162...` view save

user output
(empty)

Test 43

Verdict: TIME LIMIT EXCEEDED

input
`900 793 286 814 824 112 575 524 54...` view save

correct output
`40 835 125 199 491 175 355 624...` view save

user output
(empty)

Test 44

Verdict: TIME LIMIT EXCEEDED

input
`900 86 520 750 436 711 598 268 322...` view save

correct output
`485 569 557 653 321 748 277 12...` view save

user output
(empty)

Test 45

Verdict: TIME LIMIT EXCEEDED

input
`900 3 211 842 343 877 364 381 214 ...` view save

correct output
`335 639 155 81 727 888 416 752...` view save

user output
(empty)

Test 46

Verdict: TIME LIMIT EXCEEDED

input
`900 685 497 629 389 831 507 57 228...` view save

correct output
`425 843 342 667 650 180 448 57...` view save

user output
(empty)

Test 47

Verdict: TIME LIMIT EXCEEDED

input
`900 158 489 267 475 847 29 542 314...` view save

correct output
`467 792 741 221 125 49 266 887...` view save

user output
(empty)

Test 48

Verdict: TIME LIMIT EXCEEDED

input
`1000 588 544 250 749 769 456 423 98...` view save

correct output
`329 138 847 4 250 240 598 786 ...` view save

user output
(empty)

Test 49

Verdict: TIME LIMIT EXCEEDED

input
`1000 998 174 882 645 585 920 107 17...` view save

correct output
`180 42 847 338 228 166 612 827...` view save

user output
(empty)

Test 50

Verdict: TIME LIMIT EXCEEDED

input
`1000 805 235 974 610 433 854 903 20...` view save

correct output
`126 86 658 500 711 231 921 615...` view save

user output
(empty)

Test 51

Verdict: TIME LIMIT EXCEEDED

input
`1000 598 148 206 204 622 95 358 928...` view save

correct output
`296 283 952 288 354 907 915 77...` view save

user output
(empty)

Test 52

Verdict: TIME LIMIT EXCEEDED

input
`1000 490 683 469 136 805 544 246 51...` view save

correct output
`31 957 649 565 32 475 315 811 ...` view save

user output
(empty)

Test 53

Verdict: TIME LIMIT EXCEEDED

input
`100000 4944 311 69209 28682 87084 233...` view save

correct output
`78792 8393 13826 63615 17735 1...` view save

user output
(empty)

Test 54

Verdict: TIME LIMIT EXCEEDED

input
`100000 34704 25911 59988 65186 29855 ...` view save

correct output
`44265 90477 6685 27459 49090 5...` view save

user output
(empty)

Test 55

Verdict: TIME LIMIT EXCEEDED

input
`100000 32646 4868 34091 77349 54878 6...` view save

correct output
`69142 94411 68862 51664 42109 ...` view save

user output
(empty)

Test 56

Verdict: TIME LIMIT EXCEEDED

input
`100000 50383 56465 63211 49461 99139 ...` view save

correct output
`95420 71427 95626 67011 82375 ...` view save

user output
(empty)

Test 57

Verdict: TIME LIMIT EXCEEDED

input
`100000 94540 25313 57758 7201 51119 4...` view save

correct output
`79187 70032 63831 69384 51604 ...` view save

user output
(empty)

Test 58

Verdict: TIME LIMIT EXCEEDED

input
`100000 14300 28427 96935 52311 13463 ...` view save

correct output
`5395 57047 3087 83662 90503 24...` view save

user output
(empty)

Test 59

Verdict: TIME LIMIT EXCEEDED

input
`100000 14543 20265 6813 97256 2007 32...` view save

correct output
`16434 64136 27052 56089 37320 ...` view save

user output
(empty)

Test 60

Verdict: TIME LIMIT EXCEEDED

input
`100000 87233 22493 10433 86194 52186 ...` view save

correct output
`62003 25428 66260 57053 59291 ...` view save

user output
(empty)

Test 61

Verdict: TIME LIMIT EXCEEDED

input
`100000 83612 41781 34903 19741 34951 ...` view save

correct output
`29843 44886 70357 52228 52247 ...` view save

user output
(empty)

Test 62

Verdict: TIME LIMIT EXCEEDED

input
`99995 1 2 2 4 4 6 6 8 8 10 10 12 12 ...` view save

correct output
`99995 49998 99994 49997 99993 ...` view save

user output
(empty)

Test 63

Verdict: ACCEPTED

input
`100000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

correct output
`100000 99999 99998 99997 99996...` view save

user output
`100000 99999 99998 99997 99996...` view save

Siperia opettaa 5.0

HDRF

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

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Test 62

Test 63

Tasks

Submissions (mangolassi)