제출 #558309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558309		ymm	Stations (IOI20_stations)	C++17	100 / 100	832 ms	780 KiB

stations

///
///   Standing here
///   I realize
///   You are just like me
///   Trying to make history
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

#ifndef LOCAL
#include "stations.h"
#endif

static const int N = 1010;
static vector<int> A[N];

static void dfs(int v, int p, int c, int &t, vector<int> &vec)
{
	if (!c)
		vec[v] = t++;
	for (int u : A[v])
		if (u != p)
			dfs(u, v, !c, t, vec);
	if (c)
		vec[v] = t++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
	vector<int> labels(n);
	Loop (i,0,n)
		A[i].clear();
	Loop (i,0,n-1) {
		A[v[i]].push_back(u[i]);
		A[u[i]].push_back(v[i]);
	}
	int t = 0;
	dfs(0, -1, 0, t, labels);
	return labels;
}

int find_next_station(int s, int t, vector<int> c)
{
	int l = 0, r = c.size();
	if (s < c[0]) {
		r -= !s; // excluding par
		if (t < s) // left of this sub
			return c.back();
		auto it = lower_bound(c.begin()+l, c.begin()+r, t);
		if (it == c.end()) // right of this sub
			return c.back();
		return *it;
	} else {
		l += 1; // excluding par
		if (s < t) // rifht of this sub
			return c.front();
		auto it = upper_bound(c.begin()+l, c.begin()+r, t);
		if (it == c.begin()) // left of this sub
			return c.front();
		return *--it;
	}
}

#ifdef LOCAL
int main()
{
	auto vec = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
	Loop (i,0,5)
		cout << vec[i] << ' ';
	cout << '\n';
	auto a = A[2]; for (int &x : a) {x = vec[x];} sort(a.begin(), a.end());
	cout << find_next_station(vec[2], vec[0], a) << '\n';
	a = A[1]; for (int &x : a) {x = vec[x];} sort(a.begin(), a.end());
	cout << find_next_station(vec[1], vec[3], a) << '\n';
	cout << '\n';
	a = A[0]; for (int &x : a) {x = vec[x];} sort(a.begin(), a.end());
	cout << find_next_station(vec[0], vec[4], a) << '\n';
	a = A[1]; for (int &x : a) {x = vec[x];} sort(a.begin(), a.end());
	cout << find_next_station(vec[1], vec[4], a) << '\n';
	a = A[2]; for (int &x : a) {x = vec[x];} sort(a.begin(), a.end());
	cout << find_next_station(vec[2], vec[4], a) << '\n';
}
#endif

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