Submission #312001

#	Time	Username	Problem	Language	Result	Execution time	Memory
312001		natsugirl	Stations (IOI20_stations)	C++17	100 / 100	1011 ms	1052 KiB

stations

/* by Natsu Kinmoe */
#include <bits/stdc++.h>
using namespace std;
#define SZ(x)               ((int)(x).size())
#define all(x)              (x).begin(), (x).end()
#define loop(i, n)          for(int i = 0; i < (n); i++)
#define cont(i, n)          for(int i = 1; i <= (n); i++)
#define circ(i, a, b)       for(int i = (a); i <= (b); i++)
#define range(i, a, b, c)   for(int i = (a); ((c) > 0 ? i <= (b) : i >= (b)); i += (c))
#define foreach(it, v)      for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define y0          y0O0OO00OO0OO0OO0OOO00OO0OO0O0O000OO0
#define y1          y1II11II11III11I1III11II111IIII1II1I1
#define pub         push_back
#define pob         pop_back
#define mak         make_pair
typedef long long   ll;
typedef long double lf;
const int   Inf = 0x3f3f3f3f;
const ll    INF = 0x3f3f3f3f3f3f3f3fll;
/* Source code starts here */

#include "stations.h"

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<vector<int> > nei(n);
	loop(i, n - 1) nei[u[i]].pub(v[i]), nei[v[i]].pub(u[i]);
	vector<int> res(n);
	int tmc = 0;
	function<void(int, int, int)> dfs = [&](int now, int lst, int lvl) {
		if(lvl == 0) res[now] = ++tmc;
		loop(i, SZ(nei[now])) {
			int to = nei[now][i];
			if(to == lst) continue;
			dfs(to, now, lvl ^ 1);
		}
		if(lvl == 1) res[now] = ++tmc;
	};
	dfs(0, -1, 0);
	return res;
}

int find_next_station(int s, int t, vector<int> c) {
	vector<int> cs = c;
	int fa;
	sort(all(cs));
	if(cs[0] > s) fa = cs.back(), cs.pob(), cs.insert(cs.begin(), s);
	else fa = cs[0], cs.erase(cs.begin()), cs.pub(s);
	loop(i, SZ(cs)) if(cs[i] == t) return t;
	loop(i, SZ(cs) - 1) {
		int l = cs[i], r = cs[i + 1];
		if(t >= l && t <= r) {
			if(cs[0] == s) return r;
			else return l;
		}
	}
	return fa;
}

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