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، بإيرادات سنوية تتجاوز 100 مليون. يعمل في الشركة 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.