제출 #1297270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1297270		the_commando_x	기지국 (IOI20_stations)	C++20	100 / 100	399 ms	588 KiB

stations

#include "stations.h"
#include <vector>

const int MAXN = 1000 + 10;

std::vector<std::vector<int>> adj;
std::vector<int> labels;

int counter = 0;

void dfs(int u, int parent, int parity)
{
	if (parity == 0)
		labels[u] = counter++;

	for (int v : adj[u])
		if (v != parent)
			dfs(v, u, parity ^ 1);

	if (parity == 1)
		labels[u] = counter++;
}

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

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

	dfs(0, -1, 0);
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c)
{
	if (c.size() == 1)
		return c[0];

	if (s < c[0])
	{
		if (s > t || c[c.size() - 1 - 1] < t)
			return c.back();

		for (int i = 0; i < c.size() - 1; ++i)
		{
			if (c[i] >= t)
				return c[i];
		}
	}
	else if (s > c[0])
	{
		if (s < t || c[1] > t)
			return c.front();

		c.push_back(1e9+1);
		for (int i = 1; i < c.size(); ++i)
			if (c[i] > t)
				return c[i - 1];
	}

	return c[0]; // ! impossible case - satisying compiler warning :D
}

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