Universal Cup Judging System

Universal Cup

Limite de temps : 4.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

Kuinka moni voi menestyä yhtä hyvin kuin wcysai?

Yritys R on wcysain perustama rahaa tahkoava yritys, jonka vuotuinen liikevaihto on yli 100 miljoonaa. Yritys R:ssä työskentelee $n$ työntekijää, ja jokainen työntekijä asuu talossa. Joidenkin työntekijöiden talot on yhdistetty kaksisuuntaisilla teillä. On taattu, että kenen tahansa työntekijän talosta lähtien voidaan päästä kenen tahansa muun työntekijän talolle teitä pitkin.

Työntekijät on jaettu kahteen tyyppiin: johtajiin (tyyppi A) ja työläisiin (tyyppi B). Johtaja työskentelee $a$ tuntia päivässä, kun taas työläinen työskentelee $b$ tuntia päivässä. Luonnollisesti työläisten täytyy työskennellä pidempään kuin johtajien, joten $a < b$. Jokaisella työntekijällä on työn aloitusaika $s_i$. Jos tämän työntekijän täytyy työskennellä $m$ tuntia ($m = a$ tai $m = b$), niin hänen lopetusaikansa on $t_i = s_i + m$.

Työntekijät eivät kuitenkaan koskaan halua olla kaikkein ylityöllistetyimpiä. Siksi aloittaessaan työt he tarkistavat, onko joku heidän naapureistaan (eli työntekijöistä, joiden talot ovat suoraan yhteydessä teillä) jo aloittanut työskentelyn. Vastaavasti lopettaessaan työt he tarkistavat, onko joku heidän naapureistaan vielä lopettamatta työskentelyä. Jos molemmat havainnot ovat myönteisiä, he ovat tyytyväisiä. Muodollisesti työntekijä on tyytyväinen jos ja vain jos on olemassa naapuri, jonka aloitusaika on aidosti aikaisempi kuin hänen omansa, ja on olemassa naapuri, jonka lopetusaika on aidosti myöhäisempi kuin hänen omansa (nämä kaksi naapuria voivat olla sama henkilö tai eri henkilöitä). Muussa tapauksessa työntekijä on tyytymätön, koska hän tuntee olevansa kaikkein ylityöllistetyin.

Nyt wcysain pätevänä avustajana voit vapaasti järjestää jokaisen työntekijän aloitusajan. Haluat aikatauluttaa kaikki työntekijät järkevästi niin, että tyytymättömien ihmisten määrä minimoituu. Huomaa, että voit asettaa aloitusajoiksi mitä tahansa ei-negatiivisia reaalilukuja (katso yksityiskohdat tulostemuodosta).

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^5$), testitapausten lukumäärän.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää neljä ei-negatiivista kokonaislukua $n$, $m$, $a$ ja $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), jotka vastaavat työntekijöiden lukumäärää, teiden lukumäärää, johtajien työtunteja ja työläisten työtunteja.

Seuraava rivi sisältää pituudeltaan $n$ olevan merkkijonon, joka koostuu vain merkeistä A ja B. $i$:s merkki kertoo $i$:nnen työntekijän tyypin.

Seuraavat $m$ riviä sisältävät kukin kaksi ei-negatiivista kokonaislukua $u, v$ ($1 \le u, v \le n$), jotka kuvaavat tietä.

On taattu, että jos työntekijöiden taloja pidetään solmuina ja teitä kaarina, verkossa ei ole rinnakkaisia kaaria eikä silmukoita ja se on yhtenäinen.

On taattu, että lukujen $n$ summa ja lukujen $m$ summa yli kaikkien testitapausten eivät ylitä $5 \cdot 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää $n$ ei-negatiivista kokonaislukua $s'_i$ ($0 \le s'_i \le 10^{18}$). Tarkemmin sanottuna, jos $s_i$ merkitsee aikaa, jolloin $i$:s työntekijä aloittaa työskentelyn, niin $s_i = \frac{s'_i}{10^6}$. Jos on olemassa useita optimaalisia aikatauluja, jotka minimoivat tyytymättömien ihmisten määrän, tulosta mikä tahansa niistä.

Esimerkki

Syöte 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

Tuloste 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.