Question 0-1 Graph
The editorial says to do bfs , assign all 1 weights n travel from back and if a value is greater than next, assign min. value from right.
Is there a proof why this works>?
@tourist
2 Likes
You tagged tourist for that 
5 Likes
What should be the solution for that question ?
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 so as 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 submitted a solution considering this type of test case. What i simply do is when i am doing bfs i just see if the node im going to has a the number lesser than the node im coming from , if yes then it will have distance of the node im coming from (and not + 1) .And after i have traversed the whole graph and made my dist array. I just make sure that it is non decreasing.
Please learn to read what is written above asking same question again.