Universal Cup Judging System

Universal Cup

Time Limit: 4.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

כמה אנשים כבר יכולים להיות מצליחים כמו 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.