h994: 電耗子打排球
Tags : DP SCC bitset
Accepted rate : 3人/4人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-07-30 23:14

Content

電耗子喜歡打排球,總共有 $n$ 個電耗子,而有 $m$ 個膜拜關係,如果電耗子 $a$ 膜拜電耗子 $b$,電耗子 $b$ 膜拜電耗子 $c$,那電耗子 $a$ 也會膜拜電耗子 $c$,於是我們可以知道膜拜關係是可以傳遞的,而且一個電耗子有可能膜拜到自己。

每個電耗子都有一個發電值 $e_i$,然後這些電耗子們想要組隊打排球,這時他們會選出編號 $x$ 的電耗子當隊長,然後隊長和所有膜拜隊長的電耗子都會加入這一隊。

以編號 $x$ 電耗子當隊長的排球隊的潛力值為 $V_x$,其值為所有隊員的發電值總和,現在想請你計算每個電耗子當隊長,潛力值分別是多少?也就是要你求出 $V_1\sim V_n$。

Input

第一行有兩個整數 $n, m$,代表有幾個電耗子和有多少膜拜關係。

第二行輸入 $n$ 個正整數 $e_1\sim e_n$,代表每個電耗子的發電值。

接下來 $m$ 行,每行有兩個數字 $a, b$,代表編號 $a$ 的電耗子膜拜編號 $b$ 的電耗子。在這 $m$ 筆膜拜關係裡,$a$ 與 $b$ 相異,且不會有重複的膜拜關係,也就是說不會有重複的 $(a, b)$ 出現,但是有可能會同時有 $(a, b)$ 和 $(b, a)$。

  • $1 \leq n \leq 3\times 10^4$
  • $0 \leq m \leq \min (n\times (n - 1), 5\times 10^4)$
  • $1\leq e_i \leq 10^4$
  • $1\leq a, b \leq n$
Output

輸出一行,共 $n$ 個正整數 $V_1\sim V_n$,代表編號 $1\sim$ 編號 $n$ 的電耗子當隊長的發電值。

Sample Input #1
10 12
13 24 54 78 46 48 76 84 82 41
9 7
10 8
9 1
8 3
3 5
1 7
3 6
2 1
9 5
5 9
2 4
6 2
Sample Output #1
392 251 179 329 307 227 468 125 307 41
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (1%): 2.0s , <1K
公開 測資點#1 (1%): 2.0s , <1K
公開 測資點#2 (1%): 2.0s , <1K
公開 測資點#3 (2%): 2.0s , <1K
公開 測資點#4 (4%): 2.0s , <1M
公開 測資點#5 (4%): 2.0s , <1M
公開 測資點#6 (4%): 2.0s , <1M
公開 測資點#7 (4%): 2.0s , <1M
公開 測資點#8 (4%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (11%): 2.0s , <1M
公開 測資點#11 (11%): 2.0s , <1M
公開 測資點#12 (12%): 2.0s , <1M
公開 測資點#13 (12%): 2.0s , <1M
公開 測資點#14 (12%): 2.0s , <1M
公開 測資點#15 (12%): 2.0s , <1M
Hint :

範例的圖:

因為這題的記憶體可能會很大,所以測試執行可能會 $\text{RE}$,但如果方法是好的,送出後應該會 $\text{AC}$。

更新:有人使用 $O(n^2)$ 的做法通過此題了,且秒數與預期做法差不多,所以你如果有想到 $O(n^2)$ 的做法或許可以 $\text{AC}$ 此題。

-----------------------------------------------------------------

$\color{black}{5\%:n\leq 2}\ $

$\color{black}{25\%:n\leq 1000, m\leq 2000}\ $

$\color{black}{70\%:無特別限制}\ $

Tags:
DP SCC bitset
出處:
Caido [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」