oj.uz

Submission #304940

# Submission time Handle Problem Language Result Execution time Memory
304940 2020-09-22T08:59:08 Z ecnerwala Stations (IOI20_stations) C++17
100 / 100
 1130 ms 1048 KB 
#include "stations.h"
#include <vector>
#include <cassert>
#include <cmath>
#include <algorithm>

namespace std {

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std

std::vector<int> label(int N, int K, std::vector<int> U, std::vector<int> V) {
	std::vector<std::vector<int>> adj(N);
	for (int e = 0; e < N-1; e++) {
		adj[U[e]].push_back(V[e]);
		adj[V[e]].push_back(U[e]);
	}

	std::vector<int> labels(N);

	int cur_idx = 0;
	std::y_combinator([&](auto self, int cur, int prv, bool dir) -> void {
		if (!dir) {
			labels[cur] = cur_idx++;
		}
		for (int nxt : adj[cur]) {
			if (nxt == prv) continue;
			self(nxt, cur, !dir);
		}
		if (dir) {
			labels[cur] = cur_idx++;
		}
	})(0, -1, false);

	assert(cur_idx-1 <= K);

	return labels;
}

int find_next_station(int S, int T, std::vector<int> C) {
	assert(S != T);
	assert(!C.empty());
	if (C.front() < S) {
		if (T > S || T <= C.front()) return C.front();
		auto it = --std::upper_bound(C.begin(), C.end(), T);
		return *it;
	} else {
		if (T < S || T >= C.back()) return C.back();
		auto it = std::lower_bound(C.begin(), C.end(), T);
		return *it;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 1024 KB Output is correct
2 Correct 592 ms 1024 KB Output is correct
3 Correct 1061 ms 960 KB Output is correct
4 Correct 815 ms 736 KB Output is correct
5 Correct 721 ms 640 KB Output is correct
6 Correct 568 ms 1008 KB Output is correct
7 Correct 502 ms 768 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 2 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 684 ms 768 KB Output is correct
2 Correct 752 ms 760 KB Output is correct
3 Correct 1130 ms 936 KB Output is correct
4 Correct 680 ms 640 KB Output is correct
5 Correct 738 ms 780 KB Output is correct
6 Correct 529 ms 768 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 988 KB Output is correct
2 Correct 544 ms 1048 KB Output is correct
3 Correct 1041 ms 760 KB Output is correct
4 Correct 889 ms 640 KB Output is correct
5 Correct 663 ms 800 KB Output is correct
6 Correct 679 ms 1024 KB Output is correct
7 Correct 536 ms 780 KB Output is correct
8 Correct 2 ms 660 KB Output is correct
9 Correct 6 ms 800 KB Output is correct
10 Correct 1 ms 904 KB Output is correct
11 Correct 777 ms 640 KB Output is correct
12 Correct 646 ms 1024 KB Output is correct
13 Correct 591 ms 1008 KB Output is correct
14 Correct 608 ms 732 KB Output is correct
15 Correct 55 ms 704 KB Output is correct
16 Correct 96 ms 824 KB Output is correct
17 Correct 129 ms 844 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 943 ms 640 KB Output is correct
2 Correct 975 ms 928 KB Output is correct
3 Correct 645 ms 640 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 4 ms 776 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 759 ms 880 KB Output is correct
8 Correct 1000 ms 864 KB Output is correct
9 Correct 759 ms 904 KB Output is correct
10 Correct 758 ms 640 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Correct 6 ms 672 KB Output is correct
13 Correct 6 ms 640 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 1 ms 656 KB Output is correct
16 Correct 507 ms 788 KB Output is correct
17 Correct 584 ms 872 KB Output is correct
18 Correct 532 ms 640 KB Output is correct
19 Correct 608 ms 760 KB Output is correct
20 Correct 586 ms 768 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 1024 KB Output is correct
2 Correct 704 ms 1008 KB Output is correct
3 Correct 885 ms 640 KB Output is correct
4 Correct 754 ms 768 KB Output is correct
5 Correct 714 ms 768 KB Output is correct
6 Correct 455 ms 1024 KB Output is correct
7 Correct 502 ms 776 KB Output is correct
8 Correct 2 ms 652 KB Output is correct
9 Correct 6 ms 852 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 580 ms 768 KB Output is correct
12 Correct 586 ms 896 KB Output is correct
13 Correct 939 ms 776 KB Output is correct
14 Correct 807 ms 736 KB Output is correct
15 Correct 717 ms 748 KB Output is correct
16 Correct 520 ms 744 KB Output is correct
17 Correct 806 ms 640 KB Output is correct
18 Correct 569 ms 768 KB Output is correct
19 Correct 558 ms 1024 KB Output is correct
20 Correct 647 ms 776 KB Output is correct
21 Correct 58 ms 640 KB Output is correct
22 Correct 107 ms 768 KB Output is correct
23 Correct 119 ms 768 KB Output is correct
24 Correct 5 ms 768 KB Output is correct
25 Correct 7 ms 768 KB Output is correct
26 Correct 5 ms 768 KB Output is correct
27 Correct 4 ms 776 KB Output is correct
28 Correct 1 ms 640 KB Output is correct
29 Correct 657 ms 776 KB Output is correct
30 Correct 603 ms 644 KB Output is correct
31 Correct 572 ms 748 KB Output is correct
32 Correct 655 ms 776 KB Output is correct
33 Correct 650 ms 800 KB Output is correct
34 Correct 380 ms 768 KB Output is correct
35 Correct 513 ms 988 KB Output is correct
36 Correct 555 ms 960 KB Output is correct
37 Correct 529 ms 836 KB Output is correct
38 Correct 503 ms 888 KB Output is correct
39 Correct 555 ms 860 KB Output is correct
40 Correct 623 ms 808 KB Output is correct
41 Correct 580 ms 804 KB Output is correct
42 Correct 95 ms 904 KB Output is correct
43 Correct 113 ms 776 KB Output is correct
44 Correct 135 ms 776 KB Output is correct
45 Correct 186 ms 1024 KB Output is correct
46 Correct 339 ms 1024 KB Output is correct
47 Correct 449 ms 768 KB Output is correct
48 Correct 78 ms 800 KB Output is correct
49 Correct 93 ms 928 KB Output is correct