Submission #1166844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166844		MateiKing80	Stations (IOI20_stations)	C++20	100 / 100	300 ms	568 KiB

stations

#include <bits/stdc++.h>

using namespace std;

vector<int> g[1002];
vector<int> color;
bool used[1002];
int ptr;

void dfs(int v, bool markFirst) 
{
	used[v] = true;
	if (markFirst) 
		color[v] = ptr ++;
	for (int x : g[v])
		if (!used[x]) 
			dfs(x, !markFirst);
	if (!markFirst) 
		color[v] = ptr ++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) 
{
	for (int i = 0; i < n; i ++) 
		g[i].clear();
	for (int i = 0; i < u.size(); i ++) 
	{
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	ptr = 0;
	color.resize(n, -1);
	memset(used, false, sizeof(used));
	dfs(0, true);
	return color;
}

int find_next_station(int s, int t, vector<int> st) 
{
	sort(st.begin(), st.end());
	if (s < st[0]) 
	{
		if (t < s) 
			return st.back();
		for (int x : st)
			if (t <= x)
				return x;
		return st.back();
	} 
	else 
	{
		reverse(st.begin(), st.end());
		if (t > s)
			return st.back();
		for (auto x : st)
			if (x <= t) 
				return x;
		return st.back();
	}
}

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