Universal Cup Judging System

Universal Cup

Límite de tiempo: 4.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

有多少人能像 wcysai 一樣成功?

R 公司是由 wcysai 創立的一家印鈔公司,年營收超過 1 億。R 公司有 $n$ 名員工,每位員工都住在一棟房子裡。部分員工的房子之間由雙向道路相連。保證從任意一名員工的房子出發,都可以透過道路到達其他任何員工的房子。

員工分為兩類:經理(A 類)與工人(B 類)。經理每天工作 $a$ 小時,而工人每天工作 $b$ 小時。顯然,工人的工作時間必須比經理長,因此 $a < b$。每位員工都有一個上班開始時間 $s_i$。如果該員工需要工作 $m$ 小時($m = a$ 或 $m = b$),那麼他們的下班結束時間為 $t_i = s_i + m$。

然而,員工們絕不希望自己成為最勞累的那個人。因此,當他們開始工作時,他們會檢查是否有任何鄰居(即房子透過道路直接相連的員工)已經開始工作。同樣地,當他們結束工作時,他們會檢查是否有任何鄰居尚未結束工作。如果這兩個觀察結果都是肯定的,他們就會感到滿意。正式地說,一名員工感到滿意若且唯若存在一個鄰居的開始時間嚴格早於他們,且存在一個鄰居的結束時間嚴格晚於他們(這兩個鄰居可以是同一個人,也可以是不同的人)。否則,該員工會因為覺得自己是最勞累的人而感到不滿。

現在,作為 wcysai 的得力助手,你可以自由安排每位員工的上班開始時間。你希望合理安排所有員工的時間,使得感到不滿的人數最少。請注意,你可以將開始時間設為任何非負實數(詳見輸出格式)。

輸入格式

第一行包含一個整數 $T$($1 \le T \le 10^5$),表示測試資料的組數。

對於每組測試資料,第一行包含四個非負整數 $n$、$m$、$a$ 與 $b$($1 \le n, m \le 5 \cdot 10^5$,$1 \le a < b \le 10^6$),分別表示員工人數、道路數量、經理的工作時數以及工人的工作時數。

下一行包含一個長度為 $n$ 且僅由 A 與 B 組成的字串。第 $i$ 個字元表示第 $i$ 位員工的類型。

接下來的 $m$ 行,每行包含兩個非負整數 $u, v$($1 \le u, v \le n$),表示一條道路。

保證如果將員工的房子視為頂點、道路視為邊,則該圖無重邊與自環,且是連通的。

保證所有測試資料中 $n$ 的總和以及 $m$ 的總和皆不超過 $5 \cdot 10^5$。

輸出格式

對於每組測試資料,輸出一行,包含 $n$ 個非負整數 $s'_i$($0 \le s'_i \le 10^{18}$)。具體來說,設 $s_i$ 表示第 $i$ 位員工開始工作的時間,則 $s_i = \frac{s'_i}{10^6}$。如果存在多種使不滿人數最少的最佳時間安排,輸出其中任意一種即可。

範例

輸入 1

5
2 1 1 5
AA
1 2
3 3 1 5
ABA
1 2
1 3
2 3
5 4 2 4
BABBB
1 2
1 5
2 3
2 4
6 9 1 5
BABBAB
1 2
1 3
1 4
2 6
3 4
3 5
3 6
4 5
5 6
7 7 2 5
BBAAABB
1 2
1 3
1 5
2 4
3 6
3 7
6 7

輸出 1

0 1
1 0 2
2 1 0 3 4
2 3 1 4 4000005 0
3000003 3000004 3000002 3000005 3000006 1 0

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.