Domonion's blog

By Domonion, history, 11 months ago, ,

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?

• +9

By Domonion, history, 3 years ago, ,

You are given a sequence A 1, A 2, ... , 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?

• +17

By Domonion, history, 4 years ago, translation, ,

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?

• +7

By Domonion, history, 4 years ago, translation, ,

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?