We have graph $$$G$$$ and 4 types of queries:

1. Add/Remove set of direct edges $$$(uv)$$$.
2. Mark vertex $$$v$$$.
3. Check for some vertex $$$v$$$ if there is a path from marked vertex $$$u$$$ to $$$v$$$.

$$$N \leq 100000, M \leq 1000000, queries \leq 1000$$$. Should be better $$$O(N^2)$$$, online.

There are no more than $$$1000$$$ edges in $$$1$$$ query

I have no idea how to solve this, any hint?

Вам дана последовательность A₁, A₂, ... , A_n,  - 1000 ≤ A_i ≤ 1000, 1 ≤ n ≤ 1000.

Вы можете разделить ее на подряд идущие непустые подотрезки и от каждого оставить только его сумму

.

Необходимо максимизировать сумму произведений соседних подотрезков . Если k = 1 , то сумма равна 0.

Может кто-нибудь дать хотя бы подсказку на правильное решение?

Две абсолютно одинаковых посылки — 20406009 — WA, 20406007 — OK. Единственная разница — первая компилировалась под GNU C++14, вторая — MS C++ 2010. Почему GNU не пропускает задачу?

Вопрос номер 1: Дано N точек. Необходимо найди точку(может, не принадлежащую множеству), что сумма расстояний от нее до остальных минимально. Расстояние по обычному Евклидову. Умею через два тернарника, не знаю, как пихнуть градиентный спуск. Вопрос номер 2: Cуществует точное решение для данной задачи? В интернете не нашел ничего на эту тему.

Собственно, задача такова:

Дан неориентированный взвешенный граф. Для каждой вершины найдите длину кратчайшего простого цикла, проходящего через данную вершину.

Быстрейшее решение, что у меня есть, работает за N^4

Объясните пожалуйста, что ищет алгоритм нахождения площади объединения треугольников на ЕМАХ — http://e-maxx.ru/algo/triangles_union. На примере красной линией обведено то, что найдёт этот алгоритм. Что это? И в какой задаче это можно применить. http://mirror.codeforces.com/predownloaded/e7/37/e737f09598aa7fdba8f19083a1675f984585b4c1.jpg

Смотрел ШАД Яндекс. Там в видео про геометрический поиск рассказывали про структуру данных интервальное дерево(interval tree). Позволяет решать следующую задачу за O(Log2N + k(размер ответа)): Дано множество отрезков и множество запросов. Каждый запрос характеризуется точкой. Для каждого запроса необходимо определить множество отрезков, которые содержат в себе эту точку. Я не понял, как оно строится. На Wiki тоже ничего не понял. Кто-нибудь знает что-нибудь о ней