Блог пользователя Baba

Автор Baba, 12 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится 0 Проголосовать: не нравится

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;
}