Submission #838470

#	Time	Username	Problem	Language	Result	Execution time	Memory
838470		caganyanmaz	Stations (IOI20_stations)	C++17	0 / 100	574 ms	676 KiB

stations

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

//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int MXN = 1010;
constexpr static int LOWER_BOUND = 0;
constexpr static int UPPER_BOUND = 1;
vector<int> labels, g[MXN];


int nxt;
void dfs(int node, int parent, int state)
{
	if (state == LOWER_BOUND)
		labels[node] = nxt++;
	for (int c : g[node])
		if (c != parent)
			dfs(c, node, state^1);
	if (state == UPPER_BOUND)
		labels[node] = nxt++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) 
{
	labels = vector<int>(n);
	for (int i = 0; i < n; i++)
		g[i].clear();
	for (int i = 0; i < n-1; i++)
	{
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}
	nxt = 0;
	dfs(0, 0, LOWER_BOUND);
	return labels;
}

int find_next_station(int s, int t, vector<int> c) 
{
	debug(s, t, c);
	assert(!c.empty());
	int state;
	int lb, ub, parent;
	if (s > c[0]) // Upper Bound
	{
		state = UPPER_BOUND;
		parent = c[0];
		lb = parent; // Parent
		ub = s;
	}
	else
	{
		state = LOWER_BOUND;
		parent = c.back();
		lb = s;
		ub = parent; // Parent
	}
	if (t > ub || lb > t)
		return parent;
	auto it = upper_bound(c.begin(), c.end(), t);
	if (state == UPPER_BOUND)
		it--;
	return *it;
}

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