microtony's blog

By microtony, history, 4 years ago, In English,

Unable to parse markup [type=CF_MARKDOWN]

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

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by microtony (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Nice job!!

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I think your solution for 555D is O(qlgnlgl) — since it performs binary search for O(qlgl) times.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by microtony (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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 :)

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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