Universal Cup Judging System

Universal Cup

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

Hversu margir geta orðið jafn farsælir og wcysai?

Fyrirtæki R er peningaprentunarfyrirtæki stofnað af wcysai, með árlegar tekjur upp á yfir 100 milljónir. Það starfa $n$ starfsmenn hjá Fyrirtæki R og hver starfsmaður býr í húsi. Hús sumra starfsmanna eru tengd með tvístefnu vegum. Tryggt er að ef lagt er af stað frá húsi hvaða starfsmanns sem er, þá má komast að húsi hvaða annars starfsmanns sem er eftir vegunum.

Starfsmenn skiptast í tvo flokka: stjórnendur (flokkur A) og verkamenn (flokkur B). Stjórnandi vinnur $a$ klukkustundir á dag en verkamaður vinnur $b$ klukkustundir á dag. Augljóslega þurfa verkamenn að vinna lengur en stjórnendur, þannig að $a < b$. Hver starfsmaður hefur upphafstíma vinnu $s_i$. Ef þessi starfsmaður þarf að vinna í $m$ klukkustundir ($m = a$ eða $m = b$), þá er lokatími hans $t_i = s_i + m$.

Starfsmenn vilja hins vegar aldrei vera sá sem þrælar mest. Þess vegna, þegar þeir hefja vinnu, athuga þeir hvort einhver nágranni þeirra (þ.e. starfsmenn sem búa í húsum sem eru beintengd með vegum) sé þegar byrjaður að vinna. Á sama hátt, þegar þeir ljúka vinnu, athuga þeir hvort einhver nágranni þeirra eigi enn eftir að ljúka vinnu. Ef báðar athuganirnar eru jákvæðar eru þeir ánægðir. Formlega séð er starfsmaður ánægður ef og aðeins ef til er nágranni sem byrjar strangt fyrr en hann, og til er nágranni sem lýkur vinnu strangt síðar en hann (þessir tveir nágrannar mega vera sama manneskjan eða ólíkar manneskjur). Annars verður starfsmaðurinn óánægður vegna þess að honum finnst hann vera sá sem þrælar mest.

Nú, sem hæfur aðstoðarmaður wcysai, getur þú skipulagt upphafstíma hvers starfsmanns að vild. Þú vilt skipuleggja tíma allra starfsmanna á skynsamlegan hátt þannig að fjöldi óánægðra sé lágmarkaður. Athugaðu að þú mátt velja hvaða óneikvæðu rauntölur sem er sem upphafstíma (sjá úttakssnið fyrir nánari upplýsingar).

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^5$), fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan fjórar óneikvæðar heiltölur $n$, $m$, $a$ og $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), sem tákna fjölda starfsmanna, fjölda vega, vinnustundir stjórnenda og vinnustundir verkamanna, í þessari röð.

Næsta lína inniheldur streng af lengd $n$ sem samanstendur eingöngu af A og B. $i$-ti stafurinn táknar flokk $i$-ta starfsmannsins.

Næstu $m$ línur innihalda hver um sig tvær óneikvæðar heiltölur $u, v$ ($1 \le u, v \le n$), sem tákna veg.

Tryggt er að ef litið er á hús starfsmanna sem hnúta og vegina sem leggi, þá hefur netið hvorki margfalda leggi né sjálfslykkjur, og er samanhangandi.

Tryggt er að summa $n$ og summa $m$ yfir öll prófunartilvik fari ekki yfir $5 \cdot 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur $n$ óneikvæðar heiltölur $s'_i$ ($0 \le s'_i \le 10^{18}$). Nánar tiltekið, látum $s_i$ tákna tímann þegar $i$-ti starfsmaðurinn byrjar að vinna, þá er $s_i = \frac{s'_i}{10^6}$. Ef til eru margar bestu tímaáætlanir sem lágmarka fjölda óánægðra skal prenta hverja sem er þeirra.

Dæmi

Inntak 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

Úttak 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.