CD
А, я думал ты меня реплаил))))
Size: a a a
2021 July 03
CD
Засыпаю
V🇺
видал такую тему?
CD
Вангую декомпозицию по разрезам
CD
Я вроде показывал даже, что там можно корни получать на сетках, хотя задача казалась сложноватой :)
V🇺
там кажется sqrt(n)*polylog в лучшем случае, но зато между произвольными парами
CD
да, но наверное можно корень в лог доделать?
V🇺
но кажется про разрезы в эйсиэмном коммьюнити мало кто знает в принципе, можно что-то попроще придумать для начала
V🇺
тут существенно что один из концов на границе
V🇺
в смысле внешней грани
CD
Да, скорее всего надо ещё структуры кратчайших путей учесть
V🇺
они показывают что если пройтись по кругу, дерево кратчайших путей можно поддерживать суммарно линейным числом апдейтов
CD
У меня в эту тему была смешная идея - берём рандомную вершину, BFS и если предок/потомок в дереве то ответ
V🇺
и просто его персистят по дороге
CD
Верю, на планарных должно работать и см выше ещё
CD
Вроде обсуждали, что сюда можно ещё А* тащить
V🇺
а самое смешное что статья относительно новая - 2005ый год
CD
ну я не удивлюсь, скажем, если для произвольной пары достижим полилог в среднем :)
PO
Не вкуривают, у меня двое знакомых "альфа-самцов" попали под пресс истории в виде не понимания где можно агриться, где нет. И еще знаю историю как один школьный альфа на бандюков наехал на серьезных в ситуации когда это нахуй не нужно и в могиле теперь лежит.
PO
А один-двое выживающих были до промышленной революции