- Quarantine Keyword Graph Dfs Problem Statement With The Outspreading Covid 19 Pandemic In Taiwan The Cdc Wishes To 1 (210.99 KiB) Viewed 31 times
- Quarantine Keyword Graph Dfs Problem Statement With The Outspreading Covid 19 Pandemic In Taiwan The Cdc Wishes To 2 (53.45 KiB) Viewed 31 times
the note can help me know the logic
it is important~~
Quarantine • Keyword: Graph, DFS Problem Statement With the outspreading COVID-19 pandemic in Taiwan, the CDC wishes to monitor all quarantined() citizens and positive() cases. Given every citizen's initial immunity ) and social distances(E) with others, we try to monitor the COVID-19 cases and quarantine count in Taiwan, with the following events possible to happen. All events happen in the given order. • Event 1(Positive): The event will be noted as 1 x, meaning that citizen x has tested positive for COVID-19. Here are a few regulations for that person. • If citizen x is already under quarantine, he will not be capable to spread the virus. • If citizen x is not under quarantine yet, he will go into quarantine at the end of the event, but could have spread the virus to the following people. ▪ People having a social distance of 1 with citizen , meaning they live with him/her(). ▪ They will all go into quarantine at the end of the event. ▪ Those with immunity less than 27, will also be tested positive for COVID-19. Note that there could be a chain reaction for one spreading to another and so on. ▪ People whose social distance with citizen x is greater than 1, noted here as d. ▪ Those with immunity less than I-d will also be tested positive for COVID- 19. Note that there could be a chain reaction for one spreading to another and so on. • Event 2 (Immunity Change): The event will be noted as 2 x i, meaning that citizen a's immunity I has changed to i. • Event 3 (Social Distance Change): The event will be noted as 3 x y d, meaning that the social distance between citizen and citizen y has changed to d, due to any social reasons. Note that there could be no initial social distances between citizen x and citizen y. • Event 4 (Quarantine Count Query): The event will be noted as 4, you should then output the number of people in quarantine at that moment. • Event 5 (Case Count Query): The event will be noted as 5, you should then output the number of people that tested positive to COVID-19 at that moment. AX: - Q +
Input The first line gives two integers N and M, with the former as the count of citizens and M as the count of initial social distances. The second line gives N integers I₁, I2,..., IN as the initial immunity of the N citizens. M lines follow, each line with three numbers x, y and d, indicating the initial social distance between citizen a and citizen y as d. The next line gives a count of events Q. The Q following lines are the end of the input, Each line in the form of any of the 5 events stated above. Constraints • 1 ≤ N≤ 105 • 0≤ M≤ min(N(N-1), 105) 1≤Q≤ 2 x 105 • 1 ≤ x, y ≤ N • 1 ≤ I, d≤ 10⁹ • The citizen pairs are unique in the initial social distances. Subtasks • Subtask 1 (35 points) • N, M, Q ≤ 5000 • Event types 1 and 5 are the only occurring. • Subtask 2 (26 points) • Event types 1 and 5 are the only occurring. • All social distances are greater than 1. Subtask 3 (13 points) • Event types 1, 2 and 5 are the only occurring. • All social distances are greater than 1. • Subtask 4 (14 points): Event types 1, 2, 4 and 5 are the only occurring. Subtask 5 (21 points): No further constraints. Output For every event type 4, output Quarantined: <COUNT_OF_QUARANTINED_PEOPLE> in a single line. For every event type 5, output COVID-19 Positive Cases: <COUNT_OF_POSITIVE_CASES> in a single line. AR: 216 Q +
Sample Cases Testcase #1 (For Subtask 1) - Input 77 10 5 3 15 7 20 2 6 2 10 2 1 1 13 1 321 4 5 1 535 2 7 10 4 15 5 16 5 Testcase #1 (For Subtask 1) - Output COVID-19 Positive Cases: 1 COVID-19 Positive Cases: 4 Testcase #2 (For Subtask 2 and 3) - Input 55 19487 1 2 10 234 3 1 20 1 43 252 5 25 1 12 5 14 5 頁次: 3 16 | +
Testcase #2 (For Subtask 2 and 3) - Output COVID-19 Positive Cases: 3 COVID-19 Positive Cases: 5 The positive case count would be 2 and 4 if you exclude Event 2. Testcase #3 (For Subtasks 1 to 4) - Input 77 10 5 3 15 7 20 2 6 2 10 2 1 1 1 3 1 3 2 1 4 5 1 535 2 7 10 7 15 5 4 2 19 16 4 5 Testcase #3 (For Subtasks 1 to 4) - Output COVID-19 Positive Cases: 1 Quarantined: 2 Quarantined: 6 COVID-19 Positive Cases: 5 頁次: 4 +
Testcase #4 (For All Subtasks) - Input 77 10 5 3 15 7 20 2 6 2 10 2 1 1 131 321 451 535 27 10 10 15 WNI 5 4 2 19 3272 16 4 5 14 5 Testcase #4 (For All Subtasks) - Output COVID-19 Positive Cases: 1 Quarantined: 2 Quarantined: 7 COVID-19 Positive Cases: 6 COVID-19 Positive Cases: 7 頁次: 5/6 Q +