Submission #1229146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229146		FIFI_cpp	Stations (IOI20_stations)	C++20	100 / 100	304 ms	632 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)x.size()
using namespace std;

vector<int> a;
vector<bool> ismin;
vector<vector<int>> adj;
int cnt=1;

pair<int, int> dfs(int u, int p=-1, bool mini=1) {
	if (sz(adj[u])==1 && p!=-1) {
		a[u]=10000*(cnt++);
		ismin[u]=mini;
		return {a[u], a[u]};
	}
	a[u]=0;
	if (mini) a[u]=INT_MAX;
	pair<int, int> bests={INT_MAX, 0};
	for (auto &v: adj[u]) if (v!=p) {
		auto [mn, mx]=dfs(v, u, mini^1);
		cmin(bests.fi, mn), cmax(bests.se, mx);
	}
	if (mini) a[u]=bests.fi-1, bests.fi=a[u];
	else a[u]=bests.se+1, bests.se=a[u];
	return bests;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	adj.clear(), adj.resize(n);
	for (int i=0; i<n-1; i++) adj[u[i]].pb(v[i]), adj[v[i]].pb(u[i]);
	cnt=1, a.clear(), a.resize(n, -1), ismin.clear(), ismin.resize(n, 0);
	dfs(0);
	vector<int> b=a; sort(all(b));
	map<int, int> mp;
	for (int i=0; i<n; i++) mp[b[i]]=i;
	for (int i=0; i<n; i++) a[i]=mp[a[i]];
	return a;
}

int find_next_station(int s, int t, vector<int> c) {
	if (sz(c)==1) return c[0];
	bool smax=0;
	if (*max_element(all(c))<s) smax=1;
	if (!smax) { // s: min
		if (t<s) return *max_element(all(c));
		int best=*max_element(all(c));
		for (auto u: c) if (t<=u) {
			cmin(best, u);
		}
		return best;
	} else { // s: max
		if (t>s) return *min_element(all(c));
		int best=*min_element(all(c));
		for (auto u: c) if (t>=u) {
			cmax(best, u);
		}
		return best;
	}
}

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