CSES - Siperia opettaa 5.0

CSES - Siperia opettaa 5.0 - Results

Submission details
Task:	Distribution Center
Sender:	mangolassi
Submission time:	2017-03-09 16:54:47 +0200
Language:	C++
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0

Test results
test	verdict	time
#1	WRONG ANSWER	0.03 s	details
#2	WRONG ANSWER	0.05 s	details
#3	WRONG ANSWER	0.05 s	details
#4	WRONG ANSWER	0.04 s	details
#5	WRONG ANSWER	0.04 s	details
#6	WRONG ANSWER	0.04 s	details
#7	WRONG ANSWER	0.05 s	details
#8	WRONG ANSWER	0.03 s	details
#9	TIME LIMIT EXCEEDED	--	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	WRONG ANSWER	0.04 s	details
#16	WRONG ANSWER	0.35 s	details
#17	WRONG ANSWER	0.36 s	details
#18	WRONG ANSWER	0.35 s	details
#19	WRONG ANSWER	0.36 s	details
#20	WRONG ANSWER	0.35 s	details
#21	WRONG ANSWER	0.44 s	details
#22	WRONG ANSWER	0.43 s	details
#23	WRONG ANSWER	0.42 s	details
#24	WRONG ANSWER	0.45 s	details
#25	WRONG ANSWER	0.43 s	details
#26	WRONG ANSWER	0.02 s	details
#27	WRONG ANSWER	0.03 s	details
#28	WRONG ANSWER	0.04 s	details
#29	WRONG ANSWER	0.04 s	details
#30	WRONG ANSWER	0.03 s	details
#31	RUNTIME ERROR	0.22 s	details
#32	RUNTIME ERROR	0.20 s	details
#33	RUNTIME ERROR	0.20 s	details
#34	RUNTIME ERROR	0.18 s	details
#35	RUNTIME ERROR	0.21 s	details
#36	WRONG ANSWER	0.40 s	details
#37	WRONG ANSWER	0.03 s	details
#38	WRONG ANSWER	0.04 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 = 10;
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 = 0;
		while(k > 0) {
			while((depth[cover[ai][k]] > lca) && (k < M)) {
				++k;
			}
			--k;
			ai = cover[ai][k];
		}
		k = 0;
		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: WRONG ANSWER

input
`4 3 1000 1 2000 2 3000 3` view save

correct output
`2 3 4 4` view save

user output
`2 4 3 1` view save

Test 2

Verdict: WRONG ANSWER

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

correct output
`2 4 4 2` view save

user output
`2 3 4 1` view save

Test 3

Verdict: WRONG ANSWER

input
`10 9 100 1 200 2 300 3 400 4 ...` view save

correct output
`2 3 4 5 6 7 8 9 10 10` view save

user output
`2 4 6 8 10 3 5 7 9 1` view save

Test 4

Verdict: WRONG ANSWER

input
`10 9 100 9 200 8 300 7 400 6 ...` view save

correct output
`10 10 9 8 7 6 5 4 3 2` view save

user output
`10 8 6 4 2 3 5 7 9 1` view save

Test 5

Verdict: WRONG ANSWER

input
`10 9 100 1 200 9 300 2 400 8 ...` view save

correct output
`2 3 4 5 10 10 5 4 3 2` view save

user output
`2 6 10 8 4 3 5 7 9 1` view save

Test 6

Verdict: WRONG ANSWER

input
`10 9 100 5 200 4 300 6 400 3 ...` view save

correct output
`6 6 5 4 3 3 4 5 6 6` view save

user output
`8 4 2 6 10 3 5 7 9 1` view save

Test 7

Verdict: WRONG ANSWER

input
`10 9 100 5 200 5 300 5 400 5 ...` view save

correct output
`1 1 1 1 2 2 1 1 1 1` view save

user output
`2 4 6 8 10 3 5 7 9 1` view save

Test 8

Verdict: WRONG ANSWER

input
`10 9 100 3 200 7 300 3 400 7 ...` view save

correct output
`1 1 2 2 1 1 2 2 1 1` view save

user output
`2 6 10 4 8 3 5 7 9 1` view save

Test 9

Verdict: TIME LIMIT EXCEEDED

input
`10 1 1 1` view save

correct output
`2 2 1 1 1 1 1 1 1 1` view save

user output
(empty)

Test 10

Verdict: TIME LIMIT EXCEEDED

input
`10 1 99999 1` view save

correct output
`2 2 1 1 1 1 1 1 1 1` view save

user output
(empty)

Test 11

Verdict: TIME LIMIT EXCEEDED

input
`10 1 99999 9` view save

correct output
`1 1 1 1 1 1 1 1 2 2` view save

user output
(empty)

Test 12

Verdict: TIME LIMIT EXCEEDED

input
`10 1 99999 1` view save

correct output
`2 2 1 1 1 1 1 1 1 1` view save

user output
(empty)

Test 13

Verdict: TIME LIMIT EXCEEDED

input
`100000 1 1 1` view save

correct output
`2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
(empty)

Test 14

Verdict: TIME LIMIT EXCEEDED

input
`100000 1 1 99999` view save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
(empty)

Test 15

Verdict: WRONG ANSWER

input
`3 3 1 1 2 2 3 1` view save

correct output
`3 3 3` view save

user output
`2 3 1` view save

Test 16

Verdict: WRONG ANSWER

input
`100000 99999 51613 84082 3120 88303 90089 57457 82323 36322 ...` view save

correct output
`2 3 3 1 2 2 1 2 2 1 2 3 3 2 2 ...` view save

user output
`47511 31843 39953 48953 82089 ...` view save

Test 17

Verdict: WRONG ANSWER

input
`100000 99999 55166 92759 72522 49885 91041 58065 66993 66182 ...` view save

correct output
`1 1 2 4 4 4 4 5 5 5 2 1 3 3 3 ...` view save

user output
`36767 51741 31684 84763 79966 ...` view save

Test 18

Verdict: WRONG ANSWER

input
`100000 99999 90524 19551 22558 32618 68813 64252 16920 55138 ...` view save

correct output
`2 3 3 3 3 2 2 2 3 3 3 5 5 5 1 ...` view save

user output
`74064 44257 24095 40555 73628 ...` view save

Test 19

Verdict: WRONG ANSWER

input
`100000 99999 543 67313 25302 10820 96818 55943 93056 11560 ...` view save

correct output
`1 1 2 2 2 2 3 3 3 1 3 3 4 4 2 ...` view save

user output
`21292 44196 38584 62149 78129 ...` view save

Test 20

Verdict: WRONG ANSWER

input
`100000 99999 7098 91097 88439 4005 35386 17063 1917 86090 ...` view save

correct output
`1 3 3 5 5 3 6 6 6 3 4 4 1 3 3 ...` view save

user output
`46611 98002 73458 75504 32894 ...` view save

Test 21

Verdict: WRONG ANSWER

input
`100000 99999 61671 26653 41901 6290 45318 73847 46486 71566 ...` view save

correct output
`2 2 2 2 2 4 4 2 2 4 4 4 4 5 5 ...` view save

user output
`35362 47681 38966 88651 72463 ...` view save

Test 22

Verdict: WRONG ANSWER

input
`100000 99999 46666 39205 52562 49064 91772 40120 98068 12889 ...` view save

correct output
`2 2 4 4 3 3 3 2 3 3 2 2 6 6 5 ...` view save

user output
`92609 5208 11992 68027 45289 9...` view save

Test 23

Verdict: WRONG ANSWER

input
`100000 99999 53478 77769 62382 16090 33315 61136 81654 27389 ...` view save

correct output
`1 1 1 1 4 4 3 4 4 3 3 3 3 4 4 ...` view save

user output
`94811 64751 99050 30299 44214 ...` view save

Test 24

Verdict: WRONG ANSWER

input
`100000 99999 47015 74422 77958 41967 26483 37045 52560 21334 ...` view save

correct output
`2 2 3 3 3 1 1 1 2 2 2 4 4 4 4 ...` view save

user output
`14589 32231 49184 83106 52710 ...` view save

Test 25

Verdict: WRONG ANSWER

input
`100000 99999 30444 72197 95332 46416 50857 42241 79810 99621 ...` view save

correct output
`1 1 2 2 2 4 4 4 4 6 6 2 3 3 3 ...` view save

user output
`417 15309 227 81028 25264 6958...` view save

Test 26

Verdict: WRONG ANSWER

input
`100 99999 15682 14 57251 20 83099 50 57485 33 ...` view save

correct output
`100 100 100 100 100 100 100 10...` view save

user output
`8 50 22 4 56 36 34 84 80 32 38...` view save

Test 27

Verdict: WRONG ANSWER

input
`100 99999 77171 16 89815 40 18710 40 25372 60 ...` view save

correct output
`100 100 100 100 100 100 100 10...` view save

user output
`6 60 54 68 12 100 50 64 20 58 ...` view save

Test 28

Verdict: WRONG ANSWER

input
`100 99999 69498 75 45431 25 35804 53 35830 44 ...` view save

correct output
`100 100 100 100 100 100 100 10...` view save

user output
`52 30 42 76 68 8 22 78 18 10 4...` view save

Test 29

Verdict: WRONG ANSWER

input
`100 99999 14287 85 73750 52 14953 80 27802 96 ...` view save

correct output
`100 100 100 100 100 100 100 10...` view save

user output
`6 92 38 54 16 84 48 30 50 64 2...` view save

Test 30

Verdict: WRONG ANSWER

input
`100 99999 60021 48 2240 89 45435 4 18160 44 ...` view save

correct output
`100 100 100 100 100 100 100 10...` view save

user output
`92 98 58 36 22 96 32 80 60 94 ...` view save

Test 31

Verdict: RUNTIME ERROR

input
`200000 99999 6459 28754 89524 100200 40972 165007 35542 79232 ...` view save

correct output
`2 3 3 2 2 1 1 2 2 1 1 2 2 2 2 ...` view save

user output
(empty)

Test 32

Verdict: RUNTIME ERROR

input
`200000 99999 91854 42500 34291 59129 21533 24543 12870 128293 ...` view save

correct output
`1 2 2 2 2 2 2 1 1 2 2 2 2 2 2 ...` view save

user output
(empty)

Test 33

Verdict: RUNTIME ERROR

input
`200000 99999 88029 49150 1821 18264 32450 150397 87753 44993 ...` view save

correct output
`3 3 2 1 1 1 1 1 2 2 1 1 2 3 3 ...` view save

user output
(empty)

Test 34

Verdict: RUNTIME ERROR

input
`200000 99999 18637 75106 91405 193095 10716 115503 78702 119750 ...` view save

correct output
`1 2 2 1 1 1 1 2 2 1 3 3 2 1 1 ...` view save

user output
(empty)

Test 35

Verdict: RUNTIME ERROR

input
`200000 99999 18742 152060 38942 104683 46001 85720 9675 93087 ...` view save

correct output
`1 1 1 2 3 3 1 1 1 1 1 2 4 4 2 ...` view save

user output
(empty)

Test 36

Verdict: WRONG ANSWER

input
`100000 99999 1 99999 2 99998 3 99997 4 99996 ...` view save

correct output
`100000 100000 99999 99998 9999...` view save

user output
`100000 99998 99996 99994 99992...` view save

Test 37

Verdict: WRONG ANSWER

input
`4 3 1000 1 2000 2 3000 3` view save

correct output
`2 3 4 4` view save

user output
`2 4 3 1` view save

Test 38

Verdict: WRONG ANSWER

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

correct output
`2 4 4 2` view save

user output
`2 3 4 1` view save

Siperia opettaa 5.0

Distribution Center

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

Tasks

Submissions (mangolassi)