Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

microtony's blog

By microtony, history, 5 years ago, ,

Unable to parse markup [type=CF_MARKDOWN]

• +70

 » 5 years ago, # |   +3 Auto comment: topic has been updated by microtony (previous revision, new revision, compare).
 » 5 years ago, # |   +5 Nice job!!
 » 5 years ago, # |   +18 I think your solution for 555D is O(qlgnlgl) — since it performs binary search for O(qlgl) times.
•  » » 5 years ago, # ^ |   +16 You are right, thank you.
 » 5 years ago, # |   +8 Auto comment: topic has been updated by microtony (previous revision, new revision, compare).
 » 5 years ago, # |   +5 Nice solution for C. I solved it with segment tree for maximum (with compression) and many sets and maps (11809113). For D — we can use TreeSet (Java, 11809302) for binary search :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 don't bother, it's already explained in the editorial, thanks
 » 5 years ago, # |   +17 as i'm a really good guy i decided to write div1 E editorial ;) don't forget upvotes and please forget the downvotes ;O So at first i'm going to prove if the graph we have has no cut edges and is connected we can make it strongly connected -> imagine this we do a dfs and we have a dfs tree T in this rooted tree we direct each edge to down so the root has a way to go to all vertices so for every vertice we just need a way to get to the top so we direct the back edges (all edges other than the edges in T) to upwards if we don't have anyway to get to the root then we will always have a cut edge so we can get to it :) what if the graph has cut edges and isn't connected :o if it isn't connected we just check if s[i] and t[i] are in the same component or not and after that we check every component so assume the graph is connected if we have cut edges then both vertices in the left of it and right of it cannot have a way to each other no matter what (more formally they can't be in the same strong component) anyway if we remove the cut edges the graph will have some components now our graph has no cutedges in every component we can make them strongly connected so we will asume them as a node :) so now we will add the cutedges back we WILL have a tree (why? because if it isn't a tree then we have a cycle that and the edges in it can't be a cutedge and else and if it isn't connected our assumption is wrong :O we actually tried to process different components in the initial graph so the component we have is connected) the problem is reduced to having a tree and for each s[i] and t[i] we HAVE to direct the edges from s[i] to t[i]'s path we can do this by lca like problem 191C but with two arrays up and down for any edge either its up should be zero or its down if you have any questions please ask