Submission #1229202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229202		trimkus	Stations (IOI20_stations)	C++20	100 / 100	304 ms	536 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);
	vector<int> sz(n);
	auto get_size = [&](auto& get_size, int v, int p) -> void {
		sz[v] = 1;
		for (auto& u : adj[v]) {
			if (u == p) continue;;
			get_size(get_size, u, v);
			sz[v] += sz[u];
		}
	};
	get_size(get_size,0, -1);
	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++;
		}
		int ntl = tl;
		for (auto& u : adj[i]) {
			if (p == u) continue;
			dfs(dfs, u, i, d + 1, tl, tl + sz[u] - 1);
			tl += sz[u];
		}
	};
	int tl = 0, tr = n - 1;
	dfs(dfs, 0, -1, 0, 0, sz[0] - 1);
	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[0]) { // black
		if (s < t || c[1] > 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: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 16 / 16
• Subtask 4: 10 / 10
• Subtask 5: 61 / 61