Submission #811953

#	Time	Username	Problem	Language	Result	Execution time	Memory
811953		hgmhc	Stations (IOI20_stations)	C++17	100 / 100	831 ms	768 KiB

stations

#include "stations.h"
#include <algorithm>
using namespace std;
using vi = vector<int>;

int n, c;
vector<int> adj[1000], res;

void dfs(int d=0, int s=0, int e=-1) {
	if (d&1) res[s] = c++;
	for (const auto &u : adj[s]) if (u != e) dfs(d+1,u,s);
	if (~d&1) res[s] = c++;
}

vi label(int _n, int k, vi u, vi v) {
	n = _n;
	for (int i = 0; i < n-1; ++i) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
    c=0, res.resize(n), dfs();
    for (int i = 0; i < n; ++i) adj[i].clear();
	return res;
}

int find_next_station(int s, int t, vi c) {
	bool flag = s > c[0];
	if (flag) reverse(begin(c),end(c));
	int x, y = s;
	for (const auto &u : c) {
		x = y, y = u;
		if (flag) { if (y <= t and t < x) return u; }
		else { if (x < t and t <= y) return u; }
	}
	return c.back();
}

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