Submission #1052381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052381		MercubytheFirst	Stations (IOI20_stations)	C++17	0 / 100	531 ms	1292 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);
	// cout << "Time \n--------------------\n";
	// for(int i = 0; i < n; ++i) {
	// 	cout << i << " : " << tin[i] << ' ' << tout[i] << endl;
	// }
	// cout << "\n-----------------\n";
	// cout << "Labels\n-------------------\n";
	// for(int i = 0; i < n; ++i) {
	// 	cout << i << " : " << ans[i] << endl;
	// }
	// cout << "---------------\n";
	return ans;
}


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

int find_next_station(int s, int t, std::vector<int> c) {
	using namespace query_call;
	// cout << "hi " << s << ' ' << t << " : ";
	// cout << "[";
	// for(int x : c)
	// 	cout << x << ' ';
	// cout << "] ";
	if(c.size() == 1u) {
		// printf("ans : %d\n", c[0]);
		return c[0];
	}
	const int target_time = t/2;
	// cout << target_time << endl;
	int tin = -1, tout = -1;
	if(s % 2) {
		sort(c.begin(), c.end());
		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) {
			// printf("ans : %d\n", c[0]);
			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) {
				// printf("ans : %d\n", c[i]);
				return c[i];
			}
		}
		// assert(false);
		// cout << "odd end\n";
	}
	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) {
			// printf("ans : %d\n", c[0]);
			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) {
				// printf("ans : %d\n", c[i]);
				return c[i];
			}
		}
		// cout << "even end\n";
	}
	assert(false);
	// cout << "wtf\n";
	return -1;
}

/*
1

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

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