Baba's blog

Please help me debug this code...

By Baba, 10 years ago, In English

I've been trying to solve this problem on DP and though the logic seems clear , there's some mistake in the code which i am unable to track down. I am getting a WA on test 36.

My code

Kindly help me track down the problem Thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

prev[v] = w; // there is a mistake.
1 3 1
1 4 1
1 2 2
2 5 3 //edge 4
4 5 3 //edge 5
order of edges 4 and 5 matters.

int prevW = -1;
int prevPos = 0;
for(int i = 0; i < m; ++i)
{
    int x = edges[i].x;
    int y = edges[i].y;
    int w = edges[i].w;
    if (prevW != w)
    {
        for (int j = prevPos; j < i; ++j)
            d0[edges[j].y] = d1[edges[j].y];
        prevW = w;
        prevPos = i;
    }
    if (d1[y] < d0[x] + 1)
        d1[y] = d0[x] + 1;
}
→ Reply