Submission #1248392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248392		adrilen	Stations (IOI20_stations)	C++17	69.87 / 100	305 ms	600 KiB

stations

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

int next_number = 0;
void make_labels(int p, int par, bool is_max, vector<int>&labels, vector<vector<int>>&adj )
{
	if (!is_max) labels[p] = next_number++;

	for (int i : adj[p])
	{
		if (i == par) continue;
		make_labels(i, p, !is_max, labels, adj);
	}

	if (is_max) labels[p] = next_number++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vector<vector<int>> adj(n, vector<int>());

	for (int i = 0; i < n - 1; i++) 
	{
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	vector<int> labels(n);
	make_labels(0, -1, true, labels, adj);

	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {

	if (s > c[0])
	{
		if (t > s) return c.front();
		if (t <= c.front()) return c.front();

		if (upper_bound(c.begin(), c.end(), t) == c.begin()) return c[0];
		return *prev(upper_bound(c.begin(), c.end(), t));
	} else {
		if (t < s) return c.back();
		if (t >= c.back()) return c.back();
		if (lower_bound(c.begin(), c.end(), t) == c.end()) return c[0];
		// assert(lower_bound(c.begin(), c.end(), t) != c.end());
		return *lower_bound(c.begin(), c.end(), t);
	}
}

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