Submission #304906

#	Time	Username	Problem	Language	Result	Execution time	Memory
304906		model_code	Stations (IOI20_stations)	C++17	10 / 100	1319 ms	1008 KiB

stations

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>

const int UNVISITED = -1;
const int VISITING = -2;

void recur(
	const std::vector<std::vector<int>>& adj_list, const int cur_node, 
	int *cur_label, std::vector<int> *labels) {
	
	if (labels->at(cur_node) != UNVISITED)
		return;
	
	labels->at(cur_node) = VISITING;
	
	const int in = (*cur_label)++;
	for (const int child_node: adj_list[cur_node]) 
		recur(adj_list, child_node, cur_label, labels);
	const int out = (*cur_label)++;
	
	labels->at(cur_node) = in * 1000 + out;	
}

std::vector<int> label(
	int num_stations, int max_label, 
	std::vector<int> u, std::vector<int> v) {	
    std::vector<int> labels;
	labels.resize(num_stations);
	for (int i = 0; i < num_stations; i++) 
		labels[i] = UNVISITED;
	
	std::vector<std::vector<int>> adj_list;
	for (int i = 0; i < num_stations; i++) {
		adj_list.push_back(std::vector<int>());
	}
	
	for (int i = 0; i <= num_stations - 2; i++) {
		adj_list[u[i]].push_back(v[i]);
		adj_list[v[i]].push_back(u[i]);
	}		
	
	int cur_label = 0;
	recur(adj_list, 0, &cur_label, &labels);
	
	return labels;
}

int find_next_station(
	int source, int dest, std::vector<int> neighbours) {
					
	const int in_dest = dest / 1000;
	for (unsigned int i = 1; i < neighbours.size(); i++) {
		const int neighbour = neighbours[i];
		if (neighbour == dest) {
			return dest;
		}
		const int in = neighbour / 1000;
		const int out = neighbour % 1000;
		if ((in < in_dest) && (in_dest < out))
			return neighbour;
	}
	return neighbours[0];
}

/*
int main() {
	const std::vector<int> u = {0, 1, 1, 2};
	const std::vector<int> v = {1, 2, 3, 4};
	const std::vector<int> result = label(5, 10, u, v);
	for (const int label : result) {
		printf("%d\n", label);
	}
	printf("\n");
	printf("%d\n", find_next_station(1008, 6007, {9, 2005, 6007}));
	return 0;
}

*/

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