Submission #985992

#	Time	Username	Problem	Language	Result	Execution time	Memory
985992		fv3	Stations (IOI20_stations)	C++14	100 / 100	594 ms	1528 KiB

stations

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

vector<vector<int>> adj;
vector<int> lvl, lbl;

int currentLabel;
void DFS(int index, int last)
{
	lvl[index] = lvl[last] + 1;
	
	if (lvl[index]%2==0)
	{
		// Maximum node
		lbl[index] = currentLabel--;
	}
	
	for (auto node : adj[index])
	{
		if (node == last) continue;
		DFS(node, index);
	}

	if (lvl[index]%2)
	{
		// Minimum node
		lbl[index] = currentLabel--;
	}
}

vector<int> label(int N, int K, vector<int> U, vector<int> V)
{
	// Alternate labeling (max and min subtree size)
	adj = vector<vector<int>>(N);
	lvl = vector<int>(N);
	lbl = vector<int>(N);

	for (int i = 0; i < N - 1; i++)
	{
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}

	currentLabel = N - 1;
	DFS(0, 0);

	return lbl;
}

int find_next_station(int S, int T, vector<int> C)
{
	if (C.size()==1)
		return C[0];

	if (S > C[0])
	{
		// Max node
		// Find largest smaller than T

		if (T > S || T < C[1])
			return C[0];

		int l = 1, r = C.size() - 1;
		while (l<r)
		{
			int c = (l+r+1)/2;
			if (C[c] <= T)
				l = c;
			else
				r = c - 1;
		}

		return C[l];
	}
	else
	{
		// Min node
		if (T < S || T > C[C.size()-2])
			return C.back();

		// Find smallest larger than T
		int l = 0, r = C.size() - 2;
		while (l<r)
		{
			int c = (l+r)/2;
			if (C[c] >= T)
				r = c;
			else
				l = c + 1;
		}

		return C[l];
	}
}

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