Submission #1052410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052410		MercubytheFirst	Stations (IOI20_stations)	C++17	64.59 / 100	515 ms	1272 KiB

stations

#include "stations.h"
#include <vector>
#include <bits/stdc++.h>

namespace label_call {
	using std::vector;
	using std::cout;
	using std::max;
	using std::endl;

	vector<vector<int> > g;
	int timer = 0;
	vector<int> tin, tout, ans;
	void dfs(int v, int par, int dep) {
		tin[v] = timer;
		timer += 1;
		for(int child : g[v]) {
			if(child == par) {
				continue;
			}
			dfs(child, v, dep + 1);
		}
		tout[v] = timer;
		timer += 1;

		if(dep % 2 == 1) {
			ans[v] = 2 * tout[v] + 1;
		}
		else {
			ans[v] = 2 * tin[v];
		}
	}

} // namespace label_call

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	using namespace label_call;
	g.assign(n, vector<int>());
	tin.assign(n, -1);
	tout.assign(n, -1);
	ans.assign(n, -1);
	for(int i = 0; i < n - 1; ++i) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs(0, -1, 0);
	return ans;
}


namespace query_call {
	using std::vector;
	using std::cout;
	using std::sort;
	using std::endl;
}

int find_next_station(signed s, signed t, std::vector<signed> c) {
	using namespace query_call;
	if(c.size() == 1u) {
		return c[0];
	}
	const int target_time = t/2;
	int tin = -1, tout = -1;
	if(s % 2 == 1) {
		tout = s/2;
		tin = c[1]/2 - 1;
		assert(tin != tout and tout != target_time and tin != target_time);
		if(target_time < tin or tout < target_time) {
			return c[0];
		}
		const int child_cnt = c.size();
		for(int i = child_cnt - 1; i >= 0; --i) {
			const int child_tin = c[i]/2;
			if(target_time >= child_tin) {
				return c[i];
			}
		}
	}
	else {
		sort(c.begin(), c.end(), std::greater<int>());
		tin = s/2;
		tout = c[1]/2 + 1;
		if(target_time < tin or tout < target_time) {
			return c[0];
		}
		const int child_cnt = c.size();
		for(int i = child_cnt - 1; i >= 0; --i) {
			const int child_tin = c[i]/2;
			if(target_time <= child_tin) {
				return c[i];
			}
		}
	}
	assert(false);
	return -1;
}

/*
1

5 20
0 1
1 2
1 3
2 4
6
0 3 1
3 2 1
3 4 1
1 4 2
0 1 1



1
14 60
0 1
1 2
2 3
2 4
2 5
5 6
5 7 
1 8
0 9
9 10
10 11
11 12
11 13
*/

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