Настройки поиска (Страница 1 из 2)

Переписал код, теперь работает так: есть массив int h[], если h[v]==-1, то в поддереве всё заражено, иначе это расстояние то самой далёкой незаражённой и есть функция помечающая все заражённые вершины от источника.
И в зависимости от того помечена ли вершина и какое расстояние запучкаем заражение или нет.
Это теперь проходит большинство тестов, но на некоторых всё равно падает.
В общем вот http://ideone.com/2jOOo
Можете глянуть, если не сложно? Там немного.

Спасибо , сдал с такой идеей, но повозился с тем, что если мы, считая d[v][c], даже не попытались его обновить, то  d[v][с]=-inf, а если, считая все d[v][0..2], не попытались обновить хотя бы один, то решения не существует)
И ещё с тем, что ответ - это максимум из d[root][0..2] после всего обхода, так как некоторые значения могут превратиться в -inf по пути)

У меня наконец-то дошли руки до этой задачи!
Но столкнулся с проблемами (WA) при реализации дерева отрезков в виде:
- за O(logN) на отрезке прибавлять +-1
- за O(logN) возвращать максимум на всём массиве и его номер.
При замене дерева на линейное прибавление TL на больших тестах, т.е. ошибка в дереве отрезков.
Вот функция обновления(t - массив прибавлений, tmax - максимум на подотрезке, wmax - где находится текущий максимум на подотрезке):

 void update(int v,int tL,int tR,int l,int r,int add){
    if (l>r) return;
    if (tR==tL|(tL==l&tR==r)) {t[v]+=add;tmax[v]+=add;return;}
    int tM=(tL+tR)/2;
    update(v*2,tL,tM,l,min(r,tM),add);
    update(v*2+1,tM+1,tR,max(l,tM+1),r,add);
    tmax[v]=-99999999;
    if (tmax[v]<tmax[v*2+1]) {tmax[v]=tmax[v*2+1]+t[v];wmax[v]=wmax[v*2+1];}
    if (tmax[v]<tmax[v*2]) {tmax[v]=tmax[v*2]+t[v];wmax[v]=wmax[v*2];}
 }

Весь код: http://pastebin.com/JQbFsGCD
UPD:Игнор

Получается генерируются только всевозможные формы областей, т. е. для k=3 будет
1. ###  2. #   3.##   4.#      5.   #    6. ##       ?
               #     #        ##       ##          #
               #

Спасибо за подробные ответы!
Буду пробовать.

Разве надо сортировать, если точки даны как многоугольник без самопересечений в порядке обхода против часовой стрелки?

Там же я написал что сдал её по этой ссылке (первоначальный вариант).
А другую версию не могу дать ссылку, туда вход для тех, кто ходит в кружок

Добавил проверку - ничего не изменилось(

Спасибо, уже за день сам до этого додумался:)