The problem is here. All the test cases are available if you solve the problem (you might not be able to access that link). The official editorial is here.
My solution gets WA in three of fourteen tests.
My logic is:
Each graph can be transformed to a tree which will have the same solution. This tree is constructed such that each vertex > parent of this vertex.
Initially, the tree is linear ie 1 ← 2 ← 3 ← … ← n. Then, go through the edges of the graph. For each edge (a, b) where a < b, set tree[b] = min(tree[b], a). Then, we traverse the array in reverse manner reducing values to make it a non-decreasing array. But the values are not distances, they are parent vertices. The last loop calculates the sum of distances.
void solve()
{
ll n, nf_edges;
scan(n);scan(nf_edges);
vector<ll> tree(n + 1);
for (ll i = 1; i <= n; ++i)
{
tree[i] = i - 1;
}
//print_container(tree);
ll one, two, large, small;
while (nf_edges --)
{
scan(one); scan(two);
large = max(one, two);
small = min(one, two);
tree[large] = min(tree[large], small);
}
//print_container(tree);
for (ll i = n, level = n; i > 1; i--)
{
if (level > tree[i])
{
level = tree[i];
}
else
{
tree[i] = level;
}
}
//print_container(tree);
ll summ = 0;
for (ll i = 2, mul = 0; i <= n; ++i)
{
if (tree[i - 1] != tree[i])
{
mul++;
}
summ += mul;
}
pnl(summ);
}
I’d like an explanation for why this approach is incorrect or a small test case for which my approach fails.