Submission #306104

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
306104	2020-09-24T14:06:10 Z	lolicon	Stations (IOI20_stations)	C++14	52.3205 / 100	1136 ms	1280 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>> G(n);
	vector<int> l(n), r(n), ret(n);
	for(int i = 0; i < n - 1; i++) {
		G[u[i]].push_back(v[i]);
		G[v[i]].push_back(u[i]);
	}
	int cnt = -1;
	function<void(int, int)> dfs = [&](int x, int p) {
		l[x] = ++cnt;
		for(int y : G[x]) {
			if(y == p) continue;
			dfs(y, x);
		}
		r[x] = cnt;
	};
 	dfs(0, -1);
	for(int i = 0; i < n; i++) {
		ret[i] = r[i] * 1000 + l[i];
	}
	return ret;
}

int find_next_station(int s, int t, vector<int> c) {
	int sz = c.size();
	t = t % 1000;
	sort(begin(c), end(c), [&](int a, int b){
		int la = a % 1000; int ra = a / 1000;
		int lb = b % 1000; int rb = b / 1000;
		return (ra - la) < (rb - lb);
	});
	for(int i = 0; i < sz - 1; i++) {
		int l = c[i] % 1000; 
		int r = c[i] / 1000;
		if(l <= t && t <= r) return c[i];
	}
	return c[sz - 1];
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	512 KB	Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=9000
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=0, k=1000, vertex=0, label=995000
2	Halted	0 ms	0 KB	-

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	572 ms	1024 KB	Output is correct
2	Correct	495 ms	1008 KB	Output is correct
3	Correct	981 ms	776 KB	Output is correct
4	Correct	838 ms	640 KB	Output is correct
5	Correct	730 ms	640 KB	Output is correct
6	Correct	464 ms	1024 KB	Output is correct
7	Correct	570 ms	1024 KB	Output is correct
8	Correct	3 ms	648 KB	Output is correct
9	Correct	6 ms	640 KB	Output is correct
10	Correct	2 ms	640 KB	Output is correct
11	Correct	628 ms	640 KB	Output is correct
12	Correct	519 ms	1024 KB	Output is correct
13	Correct	502 ms	1008 KB	Output is correct
14	Correct	535 ms	832 KB	Output is correct
15	Correct	64 ms	640 KB	Output is correct
16	Correct	69 ms	856 KB	Output is correct
17	Correct	112 ms	812 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1136 ms	640 KB	Output is correct
2	Correct	680 ms	640 KB	Output is correct
3	Correct	791 ms	640 KB	Output is correct
4	Correct	3 ms	644 KB	Output is correct
5	Correct	5 ms	656 KB	Output is correct
6	Correct	1 ms	644 KB	Output is correct
7	Correct	652 ms	668 KB	Output is correct
8	Correct	1016 ms	780 KB	Output is correct
9	Correct	694 ms	640 KB	Output is correct
10	Correct	621 ms	648 KB	Output is correct
11	Correct	5 ms	648 KB	Output is correct
12	Correct	5 ms	640 KB	Output is correct
13	Correct	5 ms	640 KB	Output is correct
14	Correct	4 ms	640 KB	Output is correct
15	Correct	2 ms	640 KB	Output is correct
16	Correct	723 ms	640 KB	Output is correct
17	Correct	524 ms	768 KB	Output is correct
18	Correct	486 ms	644 KB	Output is correct
19	Correct	554 ms	640 KB	Output is correct
20	Correct	648 ms	768 KB	Output is correct

Subtask #5

26.3205 / 61.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	646 ms	1008 KB	Partially correct
2	Partially correct	616 ms	1024 KB	Partially correct
3	Partially correct	956 ms	652 KB	Partially correct
4	Partially correct	755 ms	640 KB	Partially correct
5	Partially correct	815 ms	904 KB	Partially correct
6	Partially correct	524 ms	1024 KB	Partially correct
7	Partially correct	518 ms	788 KB	Partially correct
8	Partially correct	3 ms	640 KB	Partially correct
9	Partially correct	4 ms	648 KB	Partially correct
10	Partially correct	2 ms	640 KB	Partially correct
11	Partially correct	459 ms	768 KB	Partially correct
12	Partially correct	680 ms	816 KB	Partially correct
13	Partially correct	966 ms	648 KB	Partially correct
14	Partially correct	795 ms	652 KB	Partially correct
15	Partially correct	874 ms	644 KB	Partially correct
16	Partially correct	622 ms	824 KB	Partially correct
17	Partially correct	825 ms	644 KB	Partially correct
18	Partially correct	643 ms	760 KB	Partially correct
19	Partially correct	671 ms	1088 KB	Partially correct
20	Partially correct	551 ms	828 KB	Partially correct
21	Partially correct	64 ms	896 KB	Partially correct
22	Partially correct	83 ms	872 KB	Partially correct
23	Partially correct	130 ms	768 KB	Partially correct
24	Partially correct	4 ms	640 KB	Partially correct
25	Partially correct	7 ms	640 KB	Partially correct
26	Partially correct	5 ms	648 KB	Partially correct
27	Partially correct	4 ms	640 KB	Partially correct
28	Partially correct	2 ms	640 KB	Partially correct
29	Partially correct	546 ms	652 KB	Partially correct
30	Partially correct	589 ms	640 KB	Partially correct
31	Partially correct	616 ms	640 KB	Partially correct
32	Partially correct	575 ms	640 KB	Partially correct
33	Partially correct	618 ms	792 KB	Partially correct
34	Partially correct	355 ms	768 KB	Partially correct
35	Partially correct	463 ms	1280 KB	Partially correct
36	Partially correct	473 ms	1024 KB	Partially correct
37	Partially correct	519 ms	800 KB	Partially correct
38	Partially correct	502 ms	916 KB	Partially correct
39	Partially correct	464 ms	768 KB	Partially correct
40	Partially correct	456 ms	968 KB	Partially correct
41	Partially correct	473 ms	880 KB	Partially correct
42	Partially correct	69 ms	840 KB	Partially correct
43	Partially correct	115 ms	768 KB	Partially correct
44	Partially correct	146 ms	768 KB	Partially correct
45	Partially correct	168 ms	804 KB	Partially correct
46	Partially correct	331 ms	820 KB	Partially correct
47	Partially correct	331 ms	768 KB	Partially correct
48	Partially correct	72 ms	768 KB	Partially correct
49	Partially correct	73 ms	808 KB	Partially correct