Submission #305456

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
305456	2020-09-23T08:43:37 Z	myungwoo	Stations (IOI20_stations)	C++17	69.8676 / 100	918 ms	1172 KB

stations

#include <bits/stdc++.h>
#include "stations.h"
using namespace std;

vector<int> label(int N, int K, vector<int> u, vector<int> v)
{
	vector<vector<int>> con(N);
	for (int i=0;i<N-1;i++)
		con[u[i]].push_back(v[i]),
		con[v[i]].push_back(u[i]);

	vector<int> labels(N);
	function<void(int, int)> dfs;
	dfs = [&](int n, int p){
		static int idx = 0;
		if (p == -1 || !labels[p]) labels[n] = ++idx;
		for (int t: con[n]) if (t != p)
			dfs(t, n);
		if (labels[p]) labels[n] = ++idx;
	};
	dfs(0, -1);
	return labels;
}

int find_next_station(int s, int t, vector<int> c)
{
	if (c.back() < s) reverse(c.begin(), c.end());
	for (int x: c) if (min(s, x) <= t && t <= max(s, x)) return x;
	return c.back();
}

Subtask #1

0 / 5.0

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

Subtask #2

0 / 8.0

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

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	558 ms	1024 KB	Output is correct
2	Correct	486 ms	1024 KB	Output is correct
3	Correct	918 ms	776 KB	Output is correct
4	Correct	728 ms	644 KB	Output is correct
5	Correct	613 ms	640 KB	Output is correct
6	Correct	463 ms	1024 KB	Output is correct
7	Correct	446 ms	772 KB	Output is correct
8	Correct	3 ms	652 KB	Output is correct
9	Correct	4 ms	640 KB	Output is correct
10	Correct	1 ms	652 KB	Output is correct
11	Correct	600 ms	640 KB	Output is correct
12	Correct	471 ms	1172 KB	Output is correct
13	Correct	492 ms	1120 KB	Output is correct
14	Correct	475 ms	820 KB	Output is correct
15	Correct	55 ms	768 KB	Output is correct
16	Correct	73 ms	768 KB	Output is correct
17	Correct	112 ms	824 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	896 ms	652 KB	Output is correct
2	Correct	673 ms	640 KB	Output is correct
3	Correct	593 ms	792 KB	Output is correct
4	Correct	3 ms	768 KB	Output is correct
5	Correct	5 ms	652 KB	Output is correct
6	Correct	2 ms	648 KB	Output is correct
7	Correct	596 ms	644 KB	Output is correct
8	Correct	881 ms	640 KB	Output is correct
9	Correct	691 ms	640 KB	Output is correct
10	Correct	571 ms	644 KB	Output is correct
11	Correct	7 ms	640 KB	Output is correct
12	Correct	6 ms	640 KB	Output is correct
13	Correct	6 ms	660 KB	Output is correct
14	Correct	4 ms	644 KB	Output is correct
15	Correct	2 ms	644 KB	Output is correct
16	Correct	516 ms	648 KB	Output is correct
17	Correct	519 ms	640 KB	Output is correct
18	Correct	530 ms	644 KB	Output is correct
19	Correct	552 ms	648 KB	Output is correct
20	Correct	515 ms	644 KB	Output is correct

Subtask #5

43.8676 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	548 ms	1024 KB	Partially correct
2	Partially correct	489 ms	1024 KB	Partially correct
3	Correct	901 ms	640 KB	Output is correct
4	Correct	672 ms	644 KB	Output is correct
5	Correct	627 ms	644 KB	Output is correct
6	Partially correct	477 ms	1008 KB	Partially correct
7	Correct	480 ms	788 KB	Output is correct
8	Correct	3 ms	656 KB	Output is correct
9	Correct	5 ms	640 KB	Output is correct
10	Correct	2 ms	904 KB	Output is correct
11	Partially correct	494 ms	828 KB	Partially correct
12	Partially correct	570 ms	768 KB	Partially correct
13	Correct	898 ms	660 KB	Output is correct
14	Correct	664 ms	644 KB	Output is correct
15	Correct	634 ms	776 KB	Output is correct
16	Correct	469 ms	828 KB	Output is correct
17	Correct	575 ms	640 KB	Output is correct
18	Partially correct	440 ms	788 KB	Partially correct
19	Partially correct	474 ms	1124 KB	Partially correct
20	Correct	467 ms	824 KB	Output is correct
21	Correct	58 ms	768 KB	Output is correct
22	Partially correct	71 ms	1024 KB	Partially correct
23	Partially correct	107 ms	768 KB	Partially correct
24	Correct	5 ms	652 KB	Output is correct
25	Correct	5 ms	640 KB	Output is correct
26	Correct	4 ms	640 KB	Output is correct
27	Correct	4 ms	640 KB	Output is correct
28	Correct	2 ms	652 KB	Output is correct
29	Correct	543 ms	640 KB	Output is correct
30	Correct	512 ms	644 KB	Output is correct
31	Correct	506 ms	648 KB	Output is correct
32	Correct	528 ms	652 KB	Output is correct
33	Correct	516 ms	640 KB	Output is correct
34	Partially correct	328 ms	772 KB	Partially correct
35	Partially correct	467 ms	1024 KB	Partially correct
36	Partially correct	476 ms	888 KB	Partially correct
37	Partially correct	482 ms	924 KB	Partially correct
38	Partially correct	491 ms	1016 KB	Partially correct
39	Partially correct	489 ms	788 KB	Partially correct
40	Partially correct	461 ms	928 KB	Partially correct
41	Partially correct	457 ms	800 KB	Partially correct
42	Partially correct	69 ms	768 KB	Partially correct
43	Partially correct	107 ms	816 KB	Partially correct
44	Partially correct	147 ms	768 KB	Partially correct
45	Partially correct	157 ms	816 KB	Partially correct
46	Partially correct	324 ms	824 KB	Partially correct
47	Partially correct	289 ms	800 KB	Partially correct
48	Partially correct	70 ms	952 KB	Partially correct
49	Partially correct	64 ms	816 KB	Partially correct