Submission #401992

#	Time	Username	Problem	Language	Result	Execution time	Memory
401992		mshandilya	Race (IOI11_race)	C++14	0 / 100	1 ms	332 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

long long goal;
int min_edge;
std::vector<std::list<pair<int, int>>> adj_list;
std::vector<std::unordered_map<long long, int>> dist_keymap;
std::vector<int> subtree_size;

void dfs(int root, int parent, 
	int parent_centroid, 
	int edge_dist, long long km_dist, 
	std::vector<pair<long long, int>>& subtree_dist) {
	if(dist_keymap[parent_centroid].count(goal-km_dist) and dist_keymap[parent_centroid][goal-km_dist]+edge_dist<min_edge)
		min_edge = dist_keymap[parent_centroid][goal-km_dist]+edge_dist;
	pair<long long, int> d = {km_dist, edge_dist};
	subtree_dist.emplace_back(d);
	subtree_size[root] = 1;
	for(auto& i : adj_list[root]) {
		if(i.first!=parent) {
			dfs(i.first, root, parent_centroid, edge_dist+1, km_dist+i.second, subtree_dist);
			subtree_size[root] += subtree_size[i.first];
		}
	}
	return;

}

void build_tree(int root, int tree_size) {
	int centroid = root;
	bool found = false;
	while(!found){
		found = true;
		for(auto& i : adj_list[centroid])
			if(subtree_size[i.first]>tree_size/2) {
				subtree_size[centroid] = tree_size - subtree_size[i.first];
				subtree_size[i.first] = tree_size;
				centroid = i.first;
				found = false;
			}
	}
	dist_keymap[centroid][0] = 0;
	for(auto& child : adj_list[centroid]) {
		std::list<pair<int, int>>::iterator i = adj_list[child.first].begin(); 
		for(; i!=adj_list[child.first].end(); i++)
			if((*i).first == centroid)
				break;
		adj_list[child.first].erase(i);
		std::vector<pair<long long, int>> subtree_dist;
		dfs(child.first, centroid, centroid, 1, child.second, subtree_dist);
		for(auto& i : subtree_dist) {
			if(!dist_keymap[centroid].count(i.first) or dist_keymap[centroid][i.first]>i.second)
				dist_keymap[centroid][i.first] = i.second;
		}
		build_tree(child.first, subtree_size[child.first]);
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	goal = K;
	min_edge = N+1;
	adj_list.assign(N, std::list<pair<int, int>> ());
	subtree_size.resize(N);
	dist_keymap.assign(N, unordered_map<long long, int> ());
	for(int i = 0; i<N-1; i++) {
		adj_list[H[i][0]].push_back({H[i][1], L[i]});
		adj_list[H[i][1]].push_back({H[i][0], L[i]});
	}
	std::vector<pair<long long, int>> garbage_vector;
	dfs(0, -1, 0, -N, -(long long)2e5, garbage_vector);
	build_tree(0, N);
	return min_edge;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57