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?

You are given a sequence A₁, A₂, ... , A_n,  - 1000 ≤ A_i ≤ 1000, 1 ≤ n ≤ 1000.

You can split this sequence into contiguous non-empty parts

.

Your task is to find the maximum value . If k = 1 then sum equal to 0.

Can anyone help me come up with solution?

There are 2 same submissions: 20406009 — WA, 20406007 — OK. The only diffrence is that the first submission has compiled by GNU C++14, second — MS VS 2010. Why second submission passed the tests?

Undirected weighted graph. For every vertex you should find out shortest simple cycle, which includes this vertex.

I have only O(n ^ 4) solution. Can anybody help me?