Submission #1229163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229163		trimkus	Stations (IOI20_stations)	C++20	0 / 100	302 ms	520 KiB

stations

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



std::vector<int> label(int n, int k, std::vector<int> U, std::vector<int> V) {
	vector<vector<int>> adj(n);
	for (int i = 0; i < (int)U.size(); ++i) {
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	vector<int> rt(n);
	auto dfs = [&](auto& dfs, int i, int p, int d, int& tl, int& tr) -> void {
		if (d % 2) {
			rt[i] = tr--;
		} else {
			rt[i] = tl++;
		}
		for (auto& u : adj[i]) {
			if (p == u) continue;
			dfs(dfs, u, i, d + 1, tl, tr);
		}
	};
	int tl = 0, tr = n - 1;
	dfs(dfs, 0, -1, 0, tl, tr);
	return rt;
}


int find_next_station(int s, int t, std::vector<int> c) {
	if (c.size() == 1) return c[0];
	int n = c.size();
	if (s > c.back()) { // black
		if (s < t || c[0] >= t) return c[0];
		auto it = --upper_bound(begin(c), end(c), t);
		return *it;
	} else { // white
		int right = 0;
		if (s != 0) right = c[n - 2];
		else right = c[n - 1];
		if (s > t || right > t) return c[n - 1];
		auto it = lower_bound(begin(c), end(c), t);
		return *it;
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61