Submission #457955

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
457955	2021-08-07T15:43:13 Z	rainboy	Stations (IOI20_stations)	C++17	52.3205 / 100	1329 ms	55636 KB

stations

#include "stations.h"
#include <vector>

using namespace std;
typedef vector<int> vi;

const int N = 1000;

void dfs(vector<vi> ej, vi &ta, vi &tb, int p, int i, int &time) {
	ta[i] = time++;
	for (int j : ej[i])
		if (j != p)
			dfs(ej, ta, tb, i, j, time);
	tb[i] = time - 1;
}

vi label(int n, int k, vi uu, vi vv) {
	vector<vi> ej(n);
	vi ta(n, 0), tb(n, 0), labels(n, 0);
	int h, i, time;

	for (h = 0; h < n - 1; h++) {
		ej[uu[h]].push_back(vv[h]);
		ej[vv[h]].push_back(uu[h]);
	}
	time = 0, dfs(ej, ta, tb, -1, 0, time);
	for (i = 0; i < n; i++)
		labels[i] = ta[i] * N + tb[i];
	return labels;
}

int find_next_station(int s, int t, vi cc) {
	int m = cc.size(), h;

	for (h = 0; h < m; h++)
		if (cc[h] / N > s / N && cc[h] / N <= t / N && t / N <= cc[h] % N)
			return cc[h];
	for (h = 0; h < m; h++)
		if (cc[h] / N < s / N)
			return cc[h];
	return -1;
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	327 ms	55212 KB	Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=6009
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	542 ms	792 KB	Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1511
2	Halted	0 ms	0 KB	-

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	860 ms	55420 KB	Output is correct
2	Correct	1146 ms	53072 KB	Output is correct
3	Correct	1220 ms	452 KB	Output is correct
4	Correct	781 ms	472 KB	Output is correct
5	Correct	674 ms	404 KB	Output is correct
6	Correct	1131 ms	53528 KB	Output is correct
7	Correct	559 ms	42540 KB	Output is correct
8	Correct	2 ms	468 KB	Output is correct
9	Correct	4 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	700 ms	476 KB	Output is correct
12	Correct	1115 ms	54320 KB	Output is correct
13	Correct	1291 ms	50196 KB	Output is correct
14	Correct	631 ms	3068 KB	Output is correct
15	Correct	79 ms	400 KB	Output is correct
16	Correct	229 ms	544 KB	Output is correct
17	Correct	623 ms	688 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1097 ms	400 KB	Output is correct
2	Correct	658 ms	400 KB	Output is correct
3	Correct	645 ms	400 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	5 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	703 ms	476 KB	Output is correct
8	Correct	1075 ms	400 KB	Output is correct
9	Correct	816 ms	420 KB	Output is correct
10	Correct	626 ms	468 KB	Output is correct
11	Correct	4 ms	468 KB	Output is correct
12	Correct	7 ms	468 KB	Output is correct
13	Correct	5 ms	468 KB	Output is correct
14	Correct	3 ms	468 KB	Output is correct
15	Correct	1 ms	464 KB	Output is correct
16	Correct	704 ms	476 KB	Output is correct
17	Correct	639 ms	516 KB	Output is correct
18	Correct	667 ms	400 KB	Output is correct
19	Correct	562 ms	400 KB	Output is correct
20	Correct	630 ms	604 KB	Output is correct

Subtask #5

26.3205 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	964 ms	55476 KB	Partially correct
2	Partially correct	1052 ms	48748 KB	Partially correct
3	Partially correct	1017 ms	400 KB	Partially correct
4	Partially correct	797 ms	400 KB	Partially correct
5	Partially correct	786 ms	400 KB	Partially correct
6	Partially correct	1136 ms	55392 KB	Partially correct
7	Partially correct	731 ms	31112 KB	Partially correct
8	Partially correct	3 ms	468 KB	Partially correct
9	Partially correct	5 ms	448 KB	Partially correct
10	Partially correct	0 ms	472 KB	Partially correct
11	Partially correct	1130 ms	1004 KB	Partially correct
12	Partially correct	568 ms	1108 KB	Partially correct
13	Partially correct	970 ms	400 KB	Partially correct
14	Partially correct	860 ms	472 KB	Partially correct
15	Partially correct	727 ms	400 KB	Partially correct
16	Partially correct	599 ms	1092 KB	Partially correct
17	Partially correct	611 ms	464 KB	Partially correct
18	Partially correct	1033 ms	37368 KB	Partially correct
19	Partially correct	1170 ms	51616 KB	Partially correct
20	Partially correct	536 ms	4052 KB	Partially correct
21	Partially correct	82 ms	400 KB	Partially correct
22	Partially correct	252 ms	584 KB	Partially correct
23	Partially correct	664 ms	740 KB	Partially correct
24	Partially correct	8 ms	540 KB	Partially correct
25	Partially correct	6 ms	480 KB	Partially correct
26	Partially correct	5 ms	468 KB	Partially correct
27	Partially correct	4 ms	468 KB	Partially correct
28	Partially correct	1 ms	476 KB	Partially correct
29	Partially correct	545 ms	400 KB	Partially correct
30	Partially correct	632 ms	528 KB	Partially correct
31	Partially correct	607 ms	472 KB	Partially correct
32	Partially correct	647 ms	520 KB	Partially correct
33	Partially correct	595 ms	532 KB	Partially correct
34	Partially correct	942 ms	42164 KB	Partially correct
35	Partially correct	1141 ms	55636 KB	Partially correct
36	Partially correct	1329 ms	45916 KB	Partially correct
37	Partially correct	1221 ms	13484 KB	Partially correct
38	Partially correct	1121 ms	13448 KB	Partially correct
39	Partially correct	1105 ms	18008 KB	Partially correct
40	Partially correct	1158 ms	17924 KB	Partially correct
41	Partially correct	1267 ms	14536 KB	Partially correct
42	Partially correct	369 ms	816 KB	Partially correct
43	Partially correct	622 ms	736 KB	Partially correct
44	Partially correct	651 ms	1076 KB	Partially correct
45	Partially correct	728 ms	1648 KB	Partially correct
46	Partially correct	729 ms	13960 KB	Partially correct
47	Partially correct	1049 ms	26872 KB	Partially correct
48	Partially correct	552 ms	1156 KB	Partially correct
49	Partially correct	653 ms	1024 KB	Partially correct