hackercupai/hackercup

1The starship Enterprise, bravely captained by Jean-Luc Picard, is on yet2another mission to explore strange new worlds, seek out new life and new3civilizations, and boldly go where no one has gone before! Equipped with a4state-of-the-art warp drive capable of attaining warp factor 11 and revising5the Enterprise's space-time coordinates almost at will (even sending the ship6back in time), not much can stand in the explorers' way. Though, they _are_7low on medical supplies, so they will need to first stock up on neurozine gas8for anesthetic purposes.9 10The Enterprise is heading to the Alpha Omicron solar system, which consists of11**N** planets, numbered from 1 to **N**. It also features **M** space12conduits, the _i_th of which allows the Enterprise to travel in either13direction between two different planets **Ai** and **Bi**. No two conduits14directly link the same unordered pair of planets, and **each planet is15reachable from each other planet** by following a sequence of conduits.16 17There's a geyser capable of emitting neurozine located on each planet, though18all **N** geysers are initially inactive. A sequence of **K** events will then19take place, one per hour. The event at hour _i_ is described by integers20**Ei** and **Vi**, with **Ei** indicating the event's type, which is one of21the following:22 23  * **Ei** = 1: The **Vi**th conduit (1 ≤ **Vi** ≤ **M**) collapses, and can no longer be used from that moment onwards. Each conduit collapses at most once. 24  * **Ei** = 2: The geyser on planet **Vi** (1 ≤ **Vi** ≤ **N**) activates, and begins emitting neurozine. Each geyser is activated at most once. 25  * **Ei** = 3: The geyser on planet **Vi** (1 ≤ **Vi** ≤ **N**) deactivates, and no longer emits neurozine from that moment onwards. Each geyser is deactivated at most once, and is guaranteed to not be deactivated before it has been activated. 26 27The Enterprise will arrive in the Alpha Omicron system at some planet _x_ and28just before some hour _y_. When the starship is currently at a certain planet29(and a certain time), Captain Picard may issue any of the following commands30to his crew:31 32  * Remain at that planet and wait until any future time. 33  * Travel through an uncollapsed space conduit directly from that planet to another one. Thanks to warp technology, this may be done instantly. 34  * Collect neurozine from that planet's geyser, if it's currently active. This may be done instantly. 35  * Remain at that planet while travelling backwards to any past time which is **at most 24 hours earlier than the Enterprise's original arrival time in the solar system** (in other words, the Enterprise may end up just before hour (_y_ \- 24), but no earlier). However, **this may only be done at most once**. The Enterprise retains any neurozine that it had collected before this "temporal revision". 36 37Picard wants his crew to collect neurozine from as many _different_ geysers as38possible; there's no additional value in collecting neurozine from any given39geyser multiple times, including both before and after travelling back in40time. However, Picard hasn't yet decided where and when the Enterprise should41arrive in the Alpha Omicron system. He has **S** such possible starting42situations in mind, the _i_th of which would have the Enterprise arrive at43planet **Xi** just before hour **Yi**. For each hypothetical starting44situation, please help Picard determine the maximum number of different45geysers from which the Enterprise could then proceed to collect neurozine!46 47Letting **ansi** be the answer for the _i_th starting situation, you must48output the sum of **ans1..S** in order to minimize the size of the output.49Please note that this sum may not fit within a 32-bit integer.50 51The starting situations must be considered one after another. In order to52enforce this, rather than being given **X1..S** and **Y1..S** explicitly, you53must compute them based on given values **X'1..S** and **Y'1..S**. For the54first starting situation, **X1** = **X'1** and **Y1** = **Y'1**, while for55each subsequent starting situation _i_ (2 ≤ _i_ ≤ **S**), **Xi** = **X'i** xor56**ansi-1** and **Yi** = **Y'i** xor **ansi-1** (where "xor" is the bitwise xor57operator, "^" in most programming languages).58 59### Input60 61Input begins with an integer **T**, the number of missions.  62For each mission, there is first a line containing the space-separated63integers **N**, **M**, **K** and **S**.  64Then, **M** lines follow, the _i_th of which contains the space-separated65integers **Ai** and **Bi**.  66Then, **K** lines follow, the _i_th of which contains the space-separated67integers **Ei** and **Vi**.  68Then, **S** lines follow, the _i_th of which contains the space-separated69integers **X'i** and **Y'i**.70 71### Output72 73For the _i_th mission, print a line containing "Case #_i_: " followed by one74integer, the sum of the answers for the **S** starting situations.75 76### Constraints77 781 ≤ **T** ≤ 100  792 ≤ **N** ≤ 800,000  801 ≤ **M**, **K**, **S** ≤ 800,000  811 ≤ **Ai**, **Bi** ≤ **N**  821 ≤ **Ei** ≤ 3  831 ≤ **Xi** ≤ **N**  841 ≤ **Yi** ≤ **K**  850 ≤ **X'i**, **Y'i** ≤ 1,000,000,000  86 87The sum of **N** across all **T** test cases is no greater than 2,000,000.  88The sum of **M** across all **T** test cases is no greater than 2,000,000.  89The sum of **K** across all **T** test cases is no greater than 2,000,000.  90The sum of **S** across all **T** test cases is no greater than 2,000,000.91 92### Explanation of Sample93 94In the first case, if the Enterprise arrives at planet 1 just before hour 3,95Picard could issue the following sequence of orders to help his crew collect96neurozine from both planets' geysers:97 98  1. Travel through the 1st space conduit to planet 2. 99  2. Wait until after hour 3. 100  3. Collect neurozine from planet 2's now-active geyser. 101  4. Travel back in time to just before hour 2. 102  5. Travel through the 1st space conduit to planet 1. 103  6. Collected neurozine from planet 1's active geyser. 104 105In the second case, the starting situations and corresponding answers are as106follows:107 108      i | Xi | Yi | ansi109      ------------------110      1 |  2 |  1 |    3111      2 |  1 |  6 |    2112      3 |  3 |  5 |    3113 114For the first starting situation, the Enterprise could remain on planet 2115until its geyser activates at hour 6, collect its neurozine, travel back in116time to just before hour 2, travel to planet 1 and collect its neurozine,117travel to planet 2 and then to planet 3, and remain there to collect its118neurozine after hour 5. On the other hand, for the second starting situation,119neurozine from all 3 geysers cannot be collected.120 121In the third case, the starting situations and corresponding answers are as122follows:123 124      i | Xi | Yi | ansi125      ------------------126      1 |  1 |  4 |    4127      2 |  5 |  8 |    3128      3 |  2 |  9 |    3129      4 |  3 |  6 |    4130 131In the fourth case, the starting situations and corresponding answers are as132follows:133 134      i | Xi | Yi | ansi135      ------------------136      1 |  6 | 16 |    7137      2 |  4 |  6 |    8138      3 | 10 | 22 |    7139      4 |  3 | 13 |    7140      5 |  6 | 11 |    8141      6 |  5 | 17 |    6142      7 |  2 | 21 |    7143 144In the fifth case, the first 5 starting situations and corresponding answers145are as follows:146 147      i | Xi | Yi | ansi148      ------------------149      1 | 20 | 47 |    2150      2 |  4 | 49 |    7151      3 | 24 | 47 |    1152      4 | 20 |  9 |   13153      5 |  3 | 38 |    9154 155