ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1819. Professional Approach

hint
Posted by xurshid_n 19 Jul 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 :)
Re: hint
Posted by Shen Yang 5 Dec 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
Re: hint
Posted by Shen Yang 6 Dec 2016 11:38
WA on test # 18,any one help??
Re: hint
Posted by Shen Yang 6 Dec 2016 12:44
AC 0.421s  O(n*log(n)^2)  its log(n)^2 because I use heavy_light decomposion+segment_tree
Re: hint
Posted by Shen Yang 28 Oct 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