有一種奇怪的病毒在世界蔓延,
科學家觀察以後發現該病毒具有以下特徵:
1. 病毒具有衰變性,從最開始的帶原者由內而外,最多只會往外傳播 K 層,就不會再傳播給下個人
2. 病毒可能發生變異,變異只會發生在傳播開始前,而不會發生在傳播過程中,病毒編號越大代表是越新變異的病毒
3. 曾感染過的患者會帶有抗體,除非遇到更新型變異株,否則該抗體可以抵禦相同或較舊版本病毒的攻擊
以下圖為例,
假設每次從帶原者開始最多只能往外傳播 2 層。
首先(成員1)為(病毒10)的帶原者,並將(病毒10)往外傳播,即往外傳播給(成員0、3、5)
接著(成員2)為(病毒20)的帶原者,並將(病毒20)往外傳播,即往外傳播給(成員4、3、8)
其中特別的是,(成員3)雖然已有(病毒10)的抗體,但因(病毒20)為更新型病毒(數字越大代表越新),舊的抗體不足以抵抗,仍會染疫
最後(成員7)為(病毒15)的帶原者,並將(病毒15)往外傳播,即往外傳播給(成員6、5)
其中特別的是,(成員3、8)雖然也在兩層傳播的範圍內,但因已具有更新型的(病毒20)抗體,因此不會染疫;
(成員5)則因抗體較舊,因此仍會染疫
給定人際網絡關係,與依照發生時間由前至後所觀察到的病毒帶原事件。
請計算每次事件的感染威力,即於該次事件傳播結束時,會受到該編號病毒感染的總人數(包含該次事件最初帶原者本身)。
其中你可以假設每次觀察到的病毒帶原事件,
都會在上次帶原事件傳播結束後才發生,也就是不會有兩事件同時在傳播,以致互相干擾的狀況。
並且每次病毒帶原事件的源頭都是合理的,
也就是不會有已於先前發生事件得到新型抗體,但仍成為後來發生事件舊病毒最初帶原者的狀況。
第一行有四個正整數 N, M, K, Q,
代表總人數、關聯個數、最大傳遞層數、發生的帶原事件數
1 ≤ N ≤ 1000
1 ≤ M ≤ N*(N-1)/2
1 ≤ K, Q ≤ 10
接著有 M 行,每行有兩個整數 u 和 v,
代表成員 u 和成員 v 雙向相連
0 ≤ u < v ≤ N-1
最後有 Q 行,代表由先至後所觀察到的事件。
對於每個事件有兩個整數 a 和 b,
代表於該次事件中成員 a 為病毒編號 b 的最初帶原者
0 ≤ a ≤ N-1
1 ≤ b ≤ 109
其中保證所有輸入的 b 值皆不相同,
且 b 編號越大代表為越新型變異株
印出 Q 行
每行為該次事件的感染威力,
即於該次事件傳播結束時,會受到該編號病毒感染的總人數(包含該次事件最初帶原者本身)
9 10 2 3 0 1 0 3 0 5 2 4 3 4 3 6 4 8 5 6 6 7 6 8 1 10 2 20 7 15
4 4 3
4 4 2 1 0 1 0 2 1 2 2 3 0 99999
4
10%:K = 1
30%:Q = 1
60%:無特別限制
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
35251 | mushroom.cs9 ... (mushroom) | k573 | 256 | 2023-05-19 02:38 |