Submission #1052494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052494		MercubytheFirst	Stations (IOI20_stations)	C++17	5 / 100	544 ms	940 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<int> ans;
	vector<vector<int> > g;
	void dfs(int v, int p, int d) {
		ans[v] = d;
		for(int to : g[v]) {
			if(to != p) {
				dfs(to, v, d + 1);
			}
		}
	}

} // namespace label_call

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	using namespace label_call;
	ans.assign(n, -1);
	g.assign(n, vector<int>());
	for(int i = 0; i < n - 1; ++i) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	for(int i = 0; i < n; ++i) {
		if(g[i].size() == 1u) {
			dfs(i, -1, 0);
		}
	}
	assert(count(ans.begin(), ans.end(), -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(s < t) {
		return s + 1;
	}
	return s - 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: 5 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61