Общий форум @ Timus Online Judge

andreyDagger`~ I am curious // Задача 2053. Биология 25 апр 2025 01:41

👑TIMOFEY👑`~ wa 6 // Задача 2174. Дуализм чисел 24 апр 2025 18:22

LeTim hint // Задача 1465. Игра в пешки 24 апр 2025 15:07

LeTim bad constraints // Задача 2047. Математика 23 апр 2025 15:41

DrugovaAleksandraVasilievna Язык отправки // Задача 1275. Knights of the Round Table 21 апр 2025 22:34

👑TIMOFEY👑`~ easy bfs [1] // Задача 1774. Парикмахер армии магов 5 янв 2024 16:12

Alikhan Zimanov WA 12 test [1] // Задача 1966. Велодорожки 11 апр 2020 15:08

vectorlmn If you wa on test 19 // Задача 1739. Фарюки 17 апр 2025 17:15

LeTim some tests // Задача 1519. Формула 1 17 апр 2025 15:07

vectorlmn Here are some tests. // Задача 1895. Бифштексы на борту 15 апр 2025 20:32

HappyPerson Handling Input [2] // Задача 1644. Куча орехов 23 сен 2012 01:04

Tolstobrov Anatoliy[Ivanovo SPU] Test data [2] // Задача 1739. Фарюки 10 окт 2016 19:09

coder hint [6] // Задача 1819. Профессиональный подход 19 июл 2012 14:57

3-edge connected components of graph.
A Simple 3-Edge Connected Component Algorithm by Yung H. Tsin.

But I self do not found this article :)

Shen Yang Re: hint [3] // Задача 1819. Профессиональный подход 5 дек 2016 14:26

I have a stupid idea to solve this problem:

first ,dfs a tree, then for each node compute the hash_value of edge set which cover this node..

for each query a,b if for every node on the path of (a,b) the set of edge cover by this node
is not equal to any node outside the path of (a,b) and times of edge segments covered the path >=2 then result is Yes,otherwise it is no..

I'll try to use president tree to implement this idea...

hope there is nothing wrong..

Edited by author 05.12.2016 14:35

Edited by author 05.12.2016 14:35

Shen Yang Re: hint [2] // Задача 1819. Профессиональный подход 6 дек 2016 11:38

WA on test # 18,any one help??

Shen Yang Re: hint [1] // Задача 1819. Профессиональный подход 6 дек 2016 12:44

AC 0.421s O(n*log(n)^2) its log(n)^2 because I use heavy_light decomposion+segment_tree

Shen Yang Re: hint // Задача 1819. Профессиональный подход 28 окт 2018 15:48

ccz181078 has give a random solution to the sub problem of this problem::

give a tree with n node,n<=50000 for every edege there is a color 1<=c<=50000,
give q<=50000 queries ,for each query give two node a,b judge for every color on path a-->b

this color appear only on the path a--->b ,not outside path a--->b.

sol :for every edge gives a random 32 bit number, so that for every col xor of edge with this color is zero.. for each query just judge if xor of random number on this path is zero.
if it is ,answer is Yes, otherwise it is No

~'Yamca`~ Re: hint [1] // Задача 1819. Профессиональный подход 21 фев 2025 23:12

You're wrong. The answer may be "Yes" but nodes not in one 3-edge connected component

~'Yamca`~ Re: hint // Задача 1819. Профессиональный подход 7 апр 2025 23:34

Sorry, I'm stupid, it works

~'Yamca`~ WA 7 // Задача 1819. Профессиональный подход 7 апр 2025 21:29

LeTim some tests // Задача 1859. Последний сезон Team.GOV 7 апр 2025 18:01

OpiumCat`~ WA7 // Задача 1438. Time Limit Exceeded 7 апр 2025 12:34

gio_gio What's problem with my algo??? [7] // Задача 2034. Корованы 25 окт 2014 17:36

I run 2 bfs. The first bfs starting from node S (that is caravan's distances) and the second starting from node R (that's distances from robbers). Then i recover route for caravan and on each step backward i choose node with maximum robber distance. Minimum of robber distance on the caravans path is the answer. What's wrong?

gio_gio Re: What's problem with my algo??? // Задача 2034. Корованы 26 окт 2014 16:39

I've WA on 12th test

Otrebus Re: What's problem with my algo??? [5] // Задача 2034. Корованы 8 июн 2015 18:03

It's because you can't greedily choose the node with the maximum robber distance. One of the other paths might contain a node with a smaller node distance somewhere further along. One such graph is here (this one is rather long, you probably just want to try to generate a graph that violates your greedy strategy yourself):
15 20
1 2
2 4
4 6
6 8
1 3
3 5
5 7
7 6
4 5
2 3
7 8
7 9
9 10
10 11
11 12
12 6
11 14
14 13
13 15
15 3
1 8 11

One strategy that works is to BFS backwards from the finishing vertex, and along each path you maintain the minimum robber distance. When two (or more) paths merge on some vertex, you consider the minimum of this path to be the maximum of the minimums of the two paths.

kasarino Re: What's problem with my algo??? // Задача 2034. Корованы 2 авг 2015 17:05

Otrebus, thank you for strategy !

mithun_rahman Re: What's problem with my algo??? [2] // Задача 2034. Корованы 7 ноя 2018 11:47

what will be the ans of this case, could you tell me please???

Mescalito Re: What's problem with my algo??? [1] // Задача 2034. Корованы 25 ноя 2018 00:20

3?

lodda Re: What's problem with my algo??? // Задача 2034. Корованы 16 сен 2020 21:51

i am also getting 3 for this case but wrong answer on test case #2 ..

alexocode Re: What's problem with my algo??? // Задача 2034. Корованы 2 апр 2025 18:17

That's an intersesting strategy. Now I have to find out how do you know when some paths emerge on some vertex

LeTim some tests // Задача 1555. Find the Treasure! 2 апр 2025 17:41

Geekmen Can anybody email me the dp solution? // Задача 1627. Join 1 апр 2025 14:37

Shen Yang is sample correct? [3] // Задача 1799. Саша и мажорные строки 27 дек 2016 13:43