oj.uz

Submission #304906

# Submission time Handle Problem Language Result Execution time Memory
304906 2020-09-22T07:40:17 Z model_code Stations (IOI20_stations) C++17
10 / 100
 1319 ms 1008 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 488 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=7014
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=1991
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 480 KB Invalid labels (values out of range). scenario=1, k=1000000, vertex=12, label=1750970
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1061 ms 736 KB Output is correct
2 Correct 675 ms 640 KB Output is correct
3 Correct 683 ms 904 KB Output is correct
4 Correct 3 ms 904 KB Output is correct
5 Correct 6 ms 832 KB Output is correct
6 Correct 2 ms 776 KB Output is correct
7 Correct 846 ms 744 KB Output is correct
8 Correct 1319 ms 864 KB Output is correct
9 Correct 959 ms 768 KB Output is correct
10 Correct 775 ms 768 KB Output is correct
11 Correct 4 ms 640 KB Output is correct
12 Correct 6 ms 704 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 742 ms 768 KB Output is correct
17 Correct 685 ms 768 KB Output is correct
18 Correct 629 ms 640 KB Output is correct
19 Correct 605 ms 804 KB Output is correct
20 Correct 710 ms 640 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 749 ms 1008 KB Wrong query response.
2 Halted 0 ms 0 KB -