Universal Cup Judging System

Universal Cup

时间限制: 4.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

Có bao nhiêu người có thể thành công như wcysai?

Công ty R là một công ty in tiền do wcysai sáng lập, với doanh thu hàng năm trên 100 triệu. Có $n$ nhân viên làm việc tại Công ty R, và mỗi nhân viên sống trong một ngôi nhà. Nhà của một số nhân viên được nối với nhau bằng các con đường hai chiều. Đảm bảo rằng xuất phát từ nhà của bất kỳ nhân viên nào, người ta đều có thể đi đến nhà của bất kỳ nhân viên nào khác thông qua các con đường.

Nhân viên được chia làm hai loại: quản lý (loại A) và công nhân (loại B). Một quản lý làm việc $a$ giờ mỗi ngày, trong khi một công nhân làm việc $b$ giờ mỗi ngày. Hiển nhiên, công nhân phải làm việc lâu hơn quản lý, vì vậy $a < b$. Mỗi nhân viên có thời điểm bắt đầu làm việc là $s_i$. Nếu nhân viên này cần làm việc $m$ giờ ($m = a$ hoặc $m = b$), thì thời điểm kết thúc làm việc của họ là $t_i = s_i + m$.

Tuy nhiên, các nhân viên không bao giờ muốn mình là người phải làm việc vất vả nhất. Do đó, khi bắt đầu làm việc, họ sẽ kiểm tra xem có người hàng xóm nào của mình (tức là những nhân viên có nhà được nối trực tiếp bằng đường đi) đã bắt đầu làm việc hay chưa. Tương tự, khi kết thúc công việc, họ sẽ kiểm tra xem có người hàng xóm nào của mình vẫn chưa kết thúc công việc hay không. Nếu cả hai quan sát đều cho kết quả khẳng định, họ sẽ cảm thấy hài lòng. Một cách hình thức, một nhân viên hài lòng khi và chỉ khi tồn tại một người hàng xóm có thời điểm bắt đầu sớm hơn hẳn so với họ, và tồn tại một người hàng xóm có thời điểm kết thúc muộn hơn hẳn so với họ (hai người hàng xóm này có thể là cùng một người hoặc hai người khác nhau). Ngược lại, nhân viên đó sẽ không hài lòng vì cảm thấy mình là người làm việc vất vả nhất.

Bây giờ, với tư cách là trợ lý đắc lực của wcysai, bạn có thể tự do sắp xếp thời điểm bắt đầu làm việc của mỗi nhân viên. Bạn muốn lên lịch cho tất cả nhân viên một cách hợp lý sao cho số người không hài lòng là ít nhất. Lưu ý rằng bạn có thể gán thời điểm bắt đầu là bất kỳ số thực không âm nào (xem định dạng kết quả để biết chi tiết).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^5$), là số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa bốn số nguyên không âm $n$, $m$, $a$ và $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), lần lượt biểu thị số lượng nhân viên, số lượng con đường, số giờ làm việc của quản lý và số giờ làm việc của công nhân.

Dòng tiếp theo chứa một xâu có độ dài $n$ chỉ gồm các ký tự A và B. Ký tự thứ $i$ biểu thị loại của nhân viên thứ $i$.

$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên không âm $u, v$ ($1 \le u, v \le n$), biểu thị một con đường.

Đảm bảo rằng nếu coi nhà của các nhân viên là các đỉnh và các con đường là các cạnh, thì đồ thị không có cạnh bội hay khuyên, và là đồ thị liên thông.

Đảm bảo rằng tổng của $n$ và tổng của $m$ trong tất cả các bộ dữ liệu không vượt quá $5 \cdot 10^5$.

Kết quả

Với mỗi bộ dữ liệu, in ra một dòng chứa $n$ số nguyên không âm $s'_i$ ($0 \le s'_i \le 10^{18}$). Cụ thể, gọi $s_i$ là thời điểm nhân viên thứ $i$ bắt đầu làm việc, khi đó $s_i = \frac{s'_i}{10^6}$. Nếu có nhiều lịch trình tối ưu giúp cực tiểu hóa số người không hài lòng, hãy in ra bất kỳ lịch trình nào.

Ví dụ

Dữ liệu vào 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

Kết quả 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.