Problem 175F - Gnomes of Might and Magic

Construct the graph with vertices corresponding to castles and edges to roads. Note, that a degree of each graph vertex does not exceed 4, so the amount of edges does not exceed E <= 2 * N.

In order to solve the problem let's find out how we can handle each query with time O(_log_(_N_)). Consider the query to find amount of gnomes destroyed by the Mission of Death. Assume that the edge weight is the amount of gnomes on the appropriate road. We must find the shortest path between two vertices and among them the path with the smallest amount of edges. So, the way is described by two numbers — G and R — amount of gnomes and edges (for now we do not consider lexicographical minimality). One edge between vertex u and v is described by (_C_(_u_,_v_), 1), where C(_u_,_v_) — amount of gnomes on the edge (_u_,_v_). Consider two vertices s and t. We want to find the path between them. The shortest path between them can be one of the following :

• the path along the Evil Shortcut, if both vertices are on the same Shortcut
• the path s -> g1 -> g2 -> t, where g1 и g2 — vertices on the Good Path and g1 and s are on the same Shortcut, g2 and t are on the same Shortcut (some of these 4 vertices can be identical).

So, it is necessary to determine quickly the shortest path between vertices e1 and e2 along the Evil Shortcut and between vertices g1 and g2 along the Good Path. In order to find distance between vertices along the Evil Shortcut construct for each Evil Shortcut the segment tree etree[i], which can be used to update and get the sum on the segment. For each vertex let's store the number of Evil Shortcut it belongs to and it index number on that Shortcut (it is necessary to consider cases with vertices of the Good Path, because they belong to two Shortcuts). So, the distance between two vertices of one Shortcut is the sum of edges weights of the approproate segment tree with boundaries equal to indexes of considered vertices. Similarly, construct the segment tree gtree for Good Path, by cutting it in the first vertex (for paths where it was inner vertex we will do two queries). For each pair of adjacent vertices of the Good Path we will store the minimum of two distances: distance along the edge of the Good Path or the distance along the Evil Shortcut. So for each two vertices of the Good Path the corresponding query to the segment tree returns the length (a pair of numbers) of the shortest path between two arbitrary vertices. Such a data structure allows to find the shortest path between two arbitrary vertices of the Good Path or one Evil Shortcut in time O(_log_(_N_)). It is necessary to update appropriate element of the tree with value (_0_, 1) for each pair of adjacent vertices of the Good Path initially.

Now consider the query for addition of one gnome to the edge. In order to handle this query quickly it is necessary to store amount of gnomes gsum[i] along each road of the Good Path and total number of gnomes esum[i] along each Evil Shortcut. If the gnome stands on the edge i of the Good Path, then increase gsum[i] by 1. Similarly if the gnome stands on the edge i of the Evil Shortcut, then increase esum[i] by 1 and update the appropriate value in the segment tree etree[i]. It is necessary to put new shortest path between corresponding adjacent vertices into the segment tree gtree after any of these actions because it may have changed. Note, that after removal of gnomes from the edge we can do opposite operations with the same asymptotics. So, the query for updating amount of gnomes on the edge can be handled in time O(_log_(_N_)).

Now let's figure out how we can find the shortest path between two arbitrary vertices s and t. Construct the vector of the Good Path vertices sg those we can reach from s along the edges of the Evil Shortcut which it belongs to (there will be one or two vertices in the sg ). Similarly, the vector tg contains the vertices of the Good Path those we can reach from t along the edges of the Evil Shortcut. Consider the union of vectors tsg = sg + tg. For each vertex u of the uninon let's find the vertex v1 which is the first one among vertices tsg on the path from u if we move along the edges of Good Path in the order of indexes increasing (i.e. in the order the vertices are given in the input data). Similarly, v2 is the first vertex on the opposite direction. Add to the adjacenty list of the vertex u vertices v1 and v2 with distances to them. Also, find edges (distances along the Evil Shortcuts) from s to the vertices of vector sg, and from vertices of the tg to the vertex t. If vertices s and t are on the same Evil Shortcut (and none of them is on the Good Path), then add one more direct edge from s to t, corresponding to the path along the Evil Shortcut. So we have constructed the graph which consists of not more than 6 vertices and no more than 13 edges. Start the Deijkstra algorithm on that graph to find shortest path from s to t. Note, that paths of the initial graph corresponding to edges of the new graph do not intersect in inner vertices (except, probably, a direct edge from s to t). In order to find lexicographically minimal path it is necessary to know the first inner vertex on the path corresponding to one of the edges. So we can, for example, add one more option to each path of the new graph — the vector of indexes of first vertices of the initial graph when moving along edges of a new graph. In this case 3 options (amount of gnomes, amount of edges and the vector of indexes) uniquely determines the optimal path of the Death Mission.

Now it is necessary to print the answer and find out how to handle gnome destruction on the path. Restore vertices on the optimal path. The edge between each pair of adjacent vertices is the path along the Evil Shortcut or the path between two vertices of the Good Path. In order to find gnomes on the Evil Shortcut consider the multiset eset[i] containing indexes of edges with gnomes of that Shortcut for each Evil Shortcut. Then after adding a gnome to the edge it is necessary to add the gnome index to the multiset of the Shortcut. Now all destructions of gnomes from the Evil Shortcut i, between edges l and r, can be handled by searching of iterator of the first gnome, using eset[i]._lower_bound_(_l_) and iteration, saving obtained indexes of gnomes into the list, until the value will not exceed r. After that it is necessary to remove all gnomes in the list using the algorithm described above (similarly to addition). In order to handle paths between two vertices of the Good Path, consider set gset with indexes of vertices of the Good Path that there is no path without gnomes between two adjacent vertices corresponding to indexes. After each set updating (adding/removal of the gnome) it is necessary to add the check: if the minimum distance (corresponding to the value in the segment tree gtree) is 0 (by the amount of gnomes), then it is necessary to remove appropriate index in the gset, in the opposite case it is necessary to add the index. After invocation of similar procedure (invoke gset._lower_bound_ and iterate required amount of times) we will get the list of vertices indexes going through each one we will have to destroy at least one gnome to the path to the next vertex of the Good Path (obvious, that pairs of vertices between those exists a path without gnomes should not be considered because the Death Mission will go along it without destruction of gnomes). Consider index i from this list. If for the correspondent vertex the optimal path to the next vertex of the Good Path is on the Evil Shortcut, i.e. esum[i] < gsum[i], then it is necessary to destroy all gnomes from that Shortcut using the algorithm described above. In the opposite case it is necessary to set gsum[i] = 0 and update corresponding value in the segment tree of the Shortcut gtree.

So one gnome can be removed from the path of Death Mission in O(_log_(_N_)). The amount of gnome removals does not exceed amount of added gnomes (i.e. it is not more than Q), so the complexity of one Death Mission handling is also O(_log_(_N_)). The total complexity is O(_log_(_N_) * Q).