Submission #311935

#	Time	Username	Problem	Language	Result	Execution time	Memory
311935		denverjin	기지국 (IOI20_stations)	C++14	100 / 100	1267 ms	1072 KiB

stations

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

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

vector <int> label(int n, int k, vector <int> u, vector <int> v) {
	vector <vector <int> > g(n);
	rep(i, n - 1) {
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}
	vector <int> dfn(n), ed(n), dep(n);
	int tme = 0;
	function <void(int, int)> dfs;
	dfs = [&] (int u, int p) {
		dfn[u] = tme ++;
		rep(i, g[u].size()) {
			int v = g[u][i];
			if (v == p) continue;
			dep[v] = dep[u] + 1;
			dfs(v, u);
		}
		ed[u] = tme ++;
	};
	dfs(0, -1);
	vector <int> V;
	rep(i, n) V.pb(dep[i] & 1 ? ed[i] : dfn[i]);
	sort(V.begin(), V.end());
	vector <int> lbl(n);
	rep(i, n) lbl[i] = lower_bound(V.begin(), V.end(), dep[i] & 1 ? ed[i] : dfn[i]) - V.begin();
	return lbl;
}

int find_next_station(int s, int t, vector <int> c) {
	bool dfn_ed = 0;
	rep(i, c.size()) dfn_ed |= s > c[i];
	if (dfn_ed == 0) {
		sort(c.begin(), c.end());
		rep(i, c.size() - (s != 0)) {
			int dfn = (i ? c[i - 1] : s) + 1, ed = c[i];
			if (dfn <= t && t <= ed) return c[i];
		}
		return c.back();
	} else {
		sort(c.begin(), c.end());
		rep(i, c.size()) if (i) {
			int dfn = c[i], ed = (i + 1 < (int) c.size() ? c[i + 1] : s) - 1;
			if (dfn <= t && t <= ed) return c[i];
		}
		return c[0];
	}
	return -1;
}

#ifdef DEBUG
int main() {
	vector <int> lbl = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
	cerr << find_next_station(lbl[2], lbl[0], {lbl[1], lbl[4]}) << " " << lbl[1] << endl;
	cerr << find_next_station(lbl[1], lbl[3], {lbl[0], lbl[2], lbl[3]}) << " " << lbl[3] << endl;
	return 0;
}
#endif

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