Cod sursa(job #1655444)

Utilizator andreioneaAndrei Onea andreionea Data 17 martie 2016 23:30:43
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <unordered_map>
#include <queue>
#include <fstream>
#include <vector>
#include <algorithm>

using Edge = std::pair<uint32_t, uint32_t>;
using Result = std::pair<uint32_t, uint64_t>;
using EdgeMap = std::unordered_multimap<uint64_t, uint64_t>;

class Tree
{
public:
	Tree(uint64_t N) {q.resize(N); diameter.resize(N);}
	void Insert(Edge edge)
	{
		edges.insert({edge.first, edge.second});
		edges.insert({edge.second, edge.first});
	}
	Result FarthestViaBFS(uint64_t startNode)
	{
		std::fill(diameter.begin(), diameter.end(), 0ull);
		auto currNode = startNode;
		diameter[startNode] = 1;
		size_t idx = 0;
		size_t endx = 0;
		while (true)
		{
			auto range = edges.equal_range(currNode);
			std::for_each(range.first, range.second,
				[this, &endx, currNode](EdgeMap::value_type& node)
				{
					if (!diameter[node.second])
					{
						q[endx++] = (node.second);
						diameter[node.second] = diameter[currNode] + 1;
					}
				});
			if (endx == idx)
				return {currNode, diameter[currNode]};
			currNode = q[idx++];
		}
	}
private:
	EdgeMap edges;
	std::vector<uint32_t> q;
	std::vector<uint64_t> diameter;
};

int main()
{
	std::ifstream fin("darb.in");
	std::ofstream fout("darb.out");

	uint64_t N;
	fin >> N;

	Tree t(N);

	while (N--)
	{
		uint64_t a, b;
		fin >> a >> b;
		t.Insert({a, b});
	}

	uint32_t farthest_one;
	std::tie(farthest_one, std::ignore) = t.FarthestViaBFS(1);
	uint64_t result;
	std::tie(std::ignore, result) = t.FarthestViaBFS(farthest_one);

	fout << result;

	fin.close();
	fout.close();
}