Submission #1228342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228342		Nonoze	Stations (IOI20_stations)	C++20	0 / 100	1 ms	560 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];
	ismin[u]=mini;
	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]]*2+(1-ismin[i]);
	for (int i=0; i<n; i++) cout << a[i] << ' ';
	cout << endl;
	return a;
}

int find_next_station(int s, int t, vector<int> c) {
	if (sz(c)==1) return c[0];
	// cout << s << ' ' << t << endl;
	bool tmax=t%2, smax=s%2; t/=2, s/=2; for (auto &u: c) u/=2;
	// cout << s << ' ' << t << ' ' << smax << ' ' << tmax << endl;
	if (!tmax && !smax) { // both min
		// cout << "OK" << endl;
		if (t<s) return *max_element(all(c))*2+1;
		int best=*max_element(all(c));
		for (auto u: c) if (t<=u) {
			cmin(best, u);
		}
		return best*2+1;
	} else if (tmax && smax) { // both max
		if (t>s) return *min_element(all(c))*2;
		int best=*min_element(all(c));
		for (auto u: c) if (t>=u) {
			cmax(best, u);
		}
		return best*2;
	} else if (tmax && !smax) { // t: max, s: min
		if (t>=*max_element(all(c)) || t<=s) return *max_element(all(c))*2+1;
		int best=*max_element(all(c));
		for (auto u: c) if (t<=u) {
			cmin(best, u);
		}
		return best*2+1;
	} else { // t: min, s: max
		if (t<=*min_element(all(c)) || t>=s) return *min_element(all(c))*2;
		// int cnt=0;
		// for (auto u: c) {
		// 	if (u<=t) cnt++;
		// 	if (u==t) return u*2;
		// }
		// if (cnt==1) return *min_element(all(c))*2;
		int best=*min_element(all(c));
		for (auto u: c) if (t>=u) {
			cmax(best, u);
		}
		return best*2;
	}
}

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