Submission #830974

#	Time	Username	Problem	Language	Result	Execution time	Memory
830974		Boas	Stations (IOI20_stations)	C++17	21 / 100	830 ms	884 KiB

stations

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef set<int> si;
typedef vector<si> vsi;

#define loop(x, i) for (int i = 0; i < x; i++)

#define ALL(x) (x).begin(), (x).end()

typedef pair<int, int> ii;

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
	vsi adj(n);
	loop(n - 1, i)
	{
		int a = u[i], b = v[i];
		adj[a].insert(b);
		adj[b].insert(a);
	}
	int root = 0;
	if (k == 1'000'000)
	{
		loop(n, i)
		{
			if (adj[i].size() > 2)
				root = i;
		}
	}
	else
	{
		if (k == 1000)
		{
			bool isTask2 = true;
			for (int i = 0; i < n - 1; i++)
			{
				int a = u[i], b = v[i];
				if (b > a)
					swap(a, b);
				if (a != i + 1)
				{
					isTask2 = false;
					break;
				}
				if (b != i / 2)
				{
					isTask2 = false;
					break;
				}
			}
			if (isTask2)
			{
				vector<int> labels(n, 0);
				for (int i = 1; i < n; i++)
					labels[i] = i;
				return labels;
			}
		}
		loop(n, i)
		{
			if (adj[i].size() == 1)
				root = i;
		}
	}
	vector<int> labels(n, -1);
	queue<ii> q;
	int c = 0;
	for (int i : adj[root])
	{
		q.push({i, 1 + 1000 * c});
		c++;
	}
	labels[root] = 0;
	while (!q.empty())
	{
		auto [i, d] = q.front();
		q.pop();
		labels[i] = d;
		for (int j : adj[i])
		{
			if (labels[j] != -1)
				continue;
			q.push({j, d + 1});
		}
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c)
{
	if (c.size() == 1)
		return c[0];
	if (find(ALL(c), t) != c.end())
		return t;
	vi opt1 = {(s - 1) / 2, s * 2 + 1, s * 2 + 2};
	vi opt2 = {(s - 1) / 2, s * 2 + 1};
	vi opt3 = {1, 2};
	if (c == opt1 || c == opt2 || (s == 0 && c == opt3))
	{
		int Tlevel = log2(t + 1);
		int Slevel = log2(s + 1);
		if (Tlevel <= Slevel)
			return (s - 1) / 2;
		vi branch1 = {s * 2 + 1};
		vi branch2 = {s * 2 + 2};
		while (true)
		{
			int si = branch1.size();
			bool stop = false;
			for (int i = 0; i < si; i++)
			{
				int v = branch1[i];
				branch1[i] = v * 2 + 1;
				branch1.push_back(v * 2 + 2);
				if (t == v)
					return 2 * s + 1;
				if (v > t)
				{
					stop = true;
					break;
				}
			}
			if (stop)
				break;
		}
		if (s == 0)
			return 2 * s + 2;
		while (true)
		{
			int s = branch2.size();
			bool stop = false;
			for (int i = 0; i < s; i++)
			{
				int v = branch2[i];
				branch2[i] = v * 2 + 1;
				branch2.push_back(v * 2 + 2);
				if (t == v)
					return 2 * s + 2;
				if (v > t)
				{
					stop = true;
					break;
				}
			}
			if (stop)
				break;
		}
		return (s - 1) / 2;
	}
	if (s == 0)
		return 1000 * (t / 1000) + 1;
	if (t / 1000 != s / 1000 || t < s)
		return c[0];
	return c.back();
}

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