k573. pD. 關於病毒傳播這件事
Tags : bfs flood fill
Accepted rate : 13人/13人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-05-19 02:31

Content

有一種奇怪的病毒在世界蔓延,
科學家觀察以後發現該病毒具有以下特徵:

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)則因抗體較舊,因此仍會染疫

給定人際網絡關係,與依照發生時間由前至後所觀察到的病毒帶原事件。
請計算每次事件的感染威力,即於該次事件傳播結束時,會受到該編號病毒感染的總人數(包含該次事件最初帶原者本身)。

其中你可以假設每次觀察到的病毒帶原事件,
都會在上次帶原事件傳播結束後才發生,也就是不會有兩事件同時在傳播,以致互相干擾的狀況。

並且每次病毒帶原事件的源頭都是合理的,
也就是不會有已於先前發生事件得到新型抗體,但仍成為後來發生事件舊病毒最初帶原者的狀況。

Input

第一行有四個正整數 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 編號越大代表為越新型變異株

Output

印出 Q 行
每行為該次事件的感染威力,
即於該次事件傳播結束時,會受到該編號病毒感染的總人數(包含該次事件最初帶原者本身)

Sample Input #1
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
Sample Output #1
4
4
3
Sample Input #2
4 4 2 1
0 1
0 2
1 2
2 3
0 99999
Sample Output #2
4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 2.0s , <1M
公開 測資點#1 (5%): 2.0s , <1M
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1M
公開 測資點#4 (5%): 2.0s , <1M
公開 測資點#5 (5%): 2.0s , <1M
公開 測資點#6 (5%): 2.0s , <1M
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1M
公開 測資點#12 (5%): 2.0s , <1M
公開 測資點#13 (5%): 2.0s , <1M
公開 測資點#14 (5%): 2.0s , <1M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.0s , <1M
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <1M
Hint :

10%:K = 1
30%:Q = 1
60%:無特別限制 

Tags:
bfs flood fill
出處:
112學年度hgsh校內賽 [管理者: mushroom.cs9...(mushroom) ]


ID User Problem Subject Hit Post Date
35251 mushroom.cs9...(mushroom) k573
題解
33 2023-05-19 02:38