Pagini recente » Cod sursa (job #2981809) | Cod sursa (job #2864672) | Cod sursa (job #1043799) | Cod sursa (job #1655449)
#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(int64_t 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(int64_t startNode)
{
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++];
}
}
Result FarthestViaBFS2(int64_t startNode)
{
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] > 0)
{
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<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();
}