Submission #304942

#	Time	Username	Problem	Language	Result	Execution time	Memory
304942		Namnamseo	Stations (IOI20_stations)	C++17	100 / 100	1287 ms	1284 KiB

stations

#include <vector>
#include <algorithm>
using namespace std;

vector<int> edges[1010];
int n;

vector<int> dfs(int x, int p, int d)
{
	vector<int> cv;
	for(int y:edges[x]) if (y != p) {
		auto tmp = dfs(y, x, d+1);
		cv.insert(cv.end(), tmp.begin(), tmp.end());
	}
	if (d%2 == 0) cv.insert(cv.begin(), x);
	else cv.insert(cv.end(), x);

	return cv;
}

vector<int> label(int n_, int k, vector<int> u, vector<int> v)
{
	n = n_;
	for(int i=0; i<n; ++i) edges[i].clear();

	for(int i=0; i<n-1; ++i) {
		int a = u[i], b = v[i];
		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	auto eu = dfs(0, -1, 0);

	vector<int> lbl(n);
	for(int i=0; i<n; ++i) lbl[eu[i]] = i;

	return lbl;
}

int find_next_station(int s, int t, vector<int> c)
{
	if (c.size() == 1u) return c[0];

	if (s > c[0]) {
		int sz = int(c.size()) - 1;
		c.push_back(s);
		for(int i=1; i<=sz; ++i) {
			int l = c[i], r = c[i+1]-1;
			if (l <= t && t <= r) return c[i];
		}
		return c[0];
	} else {
		rotate(c.begin(), c.end()-1, c.end());
		int sz = int(c.size()) - 1;
		c.insert(c.begin()+1, s);
		for(int i=2; i<=sz+1; ++i) {
			int r = c[i], l = c[i-1]+1;
			if (l <= t && t <= r) return c[i];
		}
		return c[0];
	}
}

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