Universal Cup Judging System

Universal Cup

시간 제한: 4.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

จะมีสักกี่คนที่ประสบความสำเร็จได้เหมือนกับ wcysai?

บริษัท R เป็นบริษัทผลิตเงินที่ก่อตั้งโดย wcysai โดยมีรายได้ต่อปีมากกว่า 100 ล้าน มีพนักงาน $n$ คนทำงานอยู่ที่บริษัท R และพนักงานแต่ละคนอาศัยอยู่ในบ้านหลังหนึ่ง บ้านของพนักงานบางคนเชื่อมต่อกันด้วยถนนสองทิศทาง รับประกันว่าเมื่อเริ่มต้นจากบ้านของพนักงานคนใดก็ตาม จะสามารถเดินทางไปยังบ้านของพนักงานคนอื่นได้ผ่านทางถนน

พนักงานแบ่งออกเป็นสองประเภท ได้แก่ ผู้จัดการ (ประเภท 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.