제출 #830935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
830935		Boas	기지국 (IOI20_stations)	C++17	21 / 100	741 ms	876 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
	{
		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 (find(ALL(c), t) != c.end())
		return t;
	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