|
|
For each vertex in tree find the nearest vertex from the way to root, in which we need to change direction. If such vertex doesn't exist, let it be -1. Let's call this vertex as bad[V], where V - some vertex in tree. To answer on query for vertex X, let's travel in "bad" array from X until we meet bad[X]=-1. Let's save visited vertices (excluding query vertex X) to some array (let's call this array "change"). Now it's quety obvious, that we need to change directions only in those visited vertices to "activate" path from root to leaf. Before changing values in "bad" array for vertex from X to root, let's take some vertex V from "change" array. Before query there was a set of vertices which have the same "bad" vertex as a V (bad[V]=bad[V_1]=bad[V_2]=...=bad[V_n], V_i - vertex from the set), and now we need to change their "bad" value to V, because we change direction in vertex V. Finally, we need to set bad[V]=-1 to all vertices from X to root. To do all operations efficiently we can use heavy-light decomposiotion + segment tree. So, the total complexity would be O(N + Q*(log(N))^2), N - number of vertices in tree. Edited by author 06.06.2019 17:11 Straightforward Link/Cut Tree solution. Just dfs the input grid and build the tree graph represented by LCT; represent paths as bamboo splay trees: just make dfs-child the right child if turnout is good and do nothing otherwise. All parents in dfs-tree that do not satisfy turnout make path parents (see LCT terminology). Now each query is just a single access—sometimes called expose—operation that saves all path parents on the path. So like, i spent a few days thinking of a possible way to do this, and one of the ideas that hit me was finding the closest parent of two vertices in O(log n) like it's done in tasks 1329 or 1471; in a case of this task, we can quickly find a parent of previous train and current train — a particular turnout that we need to switch, ignoring a potentially huge number of turnouts before this one. We switch it, make a step forward, and then repeat the algo in a subtree. Or so i thought this ideally would be. I also use the array that has, for each vertex, the trainroute that was passing by through this vertex last time. More or less, because we can't mark them all anyway, because it won't differ from a brute force then and will lead to TL. Anyways, i have found a countertest for my program: 6 6 X-L.X.X.X.X ..|.|.|.|.| S-R-R-R-R-R ..|.|.|.|.| X-R.X.X.X.F ..........| X.X.X.X.X.F |.|.|.|.|.| L-L-L-L-L-R |.|.|.|.|.| X.X.X.X.X.X 5 1 1 4 2 6 3 3 6 5 4 1 3 5 4 3 For which, my bruteforce shows a correct answer 12 2 2 2 F 3 2 3 F 4 2 4 L 5 2 4 F 6 2 3 L 6 2 5 F 7 2 3 F 11 5 5 F 12 5 5 L 12 5 4 F 14 5 5 F 16 5 3 R , but my "quick" algo doesn't have the 14 5 5 F row. It'll take too much space explaining fully why this happens, but in short, on a certain subtree it sees the route that went through that spot a bit too much time ago, and falsely assumes that further turnouts are arranged for that route. Which is not fully true. (here's a final "last visitor" map if it can potentially explain it) 00 00 00 00 00 00 03 04 03 33 33 33 00 00 00 00 00 33 00 00 00 00 00 33 00 00 33 33 35 33 00 00 00 00 00 00 So that makes me wonder, if my idea is right overall (it looked pretty to me at first...) but just my implementation is bad, or is the idea itself is a no-go and i should try something entirely different? Though quite likely i'll just give up, i spent a bit too many days on this without good outcome... |
|
|