Pagini recente » Cod sursa (job #567986) | Cod sursa (job #2128637) | Cod sursa (job #726587) | Cod sursa (job #529337) | Cod sursa (job #1655459)
#include <unordered_map>
#include <queue>
#include <fstream>
#include <vector>
#include <algorithm>
using Edge = std::pair<int, int>;
using Result = std::pair<int, int64_t>;
using EdgeMap = std::unordered_multimap<int64_t, int64_t>;
class Tree
{
public:
Tree(int N) : diameter(N, 0) {q.resize(N);}
void Insert(Edge edge)
{
edges.insert({edge.first, edge.second});
edges.insert({edge.second, edge.first});
}
Result FarthestViaBFS1(int startNode)
{
auto currNode = startNode;
diameter[startNode] = 1;
auto topQ = q.begin();
auto endQ = q.begin();
while (true)
{
auto range = edges.equal_range(currNode);
std::for_each(range.first, range.second,
[this, &endQ, &currNode](EdgeMap::value_type& node)
{
if (diameter[node.second] == 0)
{
*(endQ++) = (node.second);
diameter[node.second] = diameter[currNode] + 1;
}
});
if (q.end() == topQ)
return {currNode, diameter[currNode]};
currNode = *(topQ++);
}
}
Result FarthestViaBFS2(int startNode)
{
auto currNode = startNode;
diameter[startNode] = -1;
auto topQ = q.begin();
auto endQ = q.begin();
while (true)
{
auto range = edges.equal_range(currNode);
std::for_each(range.first, range.second,
[this, &endQ, &currNode](EdgeMap::value_type& node)
{
if (diameter[node.second] > 0)
{
*(endQ++) = (node.second);
diameter[node.second] = diameter[currNode] - 1;
}
});
if (q.end() == topQ)
return {currNode, -diameter[currNode]};
currNode = *(topQ++);
}
}
private:
EdgeMap edges;
std::vector<int> q;
std::vector<int64_t> diameter;
};
int main()
{
std::ifstream fin("darb.in");
std::ofstream fout("darb.out");
int N;
fin >> N;
Tree t(N);
while (N--)
{
int a, b;
fin >> a >> b;
t.Insert({a, b});
}
int farthest_one;
std::tie(farthest_one, std::ignore) = t.FarthestViaBFS1(1);
int64_t result;
std::tie(std::ignore, result) = t.FarthestViaBFS2(farthest_one);
fout << result;
fin.close();
fout.close();
}