Domonion's blog

By Domonion, history, 11 months ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

By Domonion, history, 3 years ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

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

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

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

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it