Submission #304944

#	Time	Username	Problem	Language	Result	Execution time	Memory
304944		ecnerwala	Stations (IOI20_stations)	C++17	100 / 100	1154 ms	1044 KiB

stations

#include "stations.h"
#include <vector>
#include <cassert>
#include <cmath>
#include <algorithm>

namespace {
void do_label(const std::vector<std::vector<int>>& adj, std::vector<int>& labels, int& cur_idx, int cur, int prv, bool dir) {
	if (!dir) {
		labels[cur] = cur_idx++;
	}
	for (int nxt : adj[cur]) {
		if (nxt == prv) continue;
		do_label(adj, labels, cur_idx, nxt, cur, !dir);
	}
	if (dir) {
		labels[cur] = cur_idx++;
	}
}
}

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;
	do_label(adj, labels, 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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 16 / 16
• Subtask 4: 10 / 10
• Subtask 5: 61 / 61