Universal Cup Judging System

Universal Cup

Süre Sınırı: 4.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Combien de personnes peuvent avoir autant de succès que wcysai ?

L'entreprise R est une véritable machine à billets fondée par wcysai, avec un chiffre d'affaires annuel de plus de 100 millions. Il y a $n$ employés qui travaillent dans l'entreprise R, et chaque employé vit dans une maison. Les maisons de certains employés sont reliées par des routes bidirectionnelles. Il est garanti qu'en partant de la maison de n'importe quel employé, on peut rejoindre la maison de n'importe quel autre employé par les routes.

Les employés sont divisés en deux catégories : les managers (type A) et les ouvriers (type B). Un manager travaille $a$ heures par jour, tandis qu'un ouvrier travaille $b$ heures par jour. Évidemment, les ouvriers doivent travailler plus longtemps que les managers, donc $a < b$. Chaque employé a une heure de début de travail $s_i$. Si cet employé doit travailler $m$ heures ($m = a$ ou $m = b$), alors son heure de fin est $t_i = s_i + m$.

Cependant, les employés ne veulent jamais être les plus surmenés. Par conséquent, lorsqu'ils commencent à travailler, ils vérifient si l'un de leurs voisins (c'est-à-dire les employés dont les maisons sont directement reliées par une route) a déjà commencé à travailler. De même, lorsqu'ils terminent leur travail, ils vérifient si l'un de leurs voisins n'a pas encore fini de travailler. Si ces deux observations sont positives, ils se sentent satisfaits. Formellement, un employé est satisfait si et seulement s'il existe un voisin dont l'heure de début est strictement antérieure à la sienne, et s'il existe un voisin dont l'heure de fin est strictement postérieure à la sienne (ces deux voisins peuvent être la même personne ou des personnes différentes). Sinon, l'employé sera insatisfait car il aura l'impression d'être le plus surmené.

Maintenant, en tant qu'assistant compétent de wcysai, vous pouvez organiser librement l'heure de début de chaque employé. Vous souhaitez planifier les horaires de tous les employés de manière raisonnable afin que le nombre de personnes insatisfaites soit minimisé. Notez que vous pouvez attribuer aux heures de début n'importe quels nombres réels positifs ou nuls (voir le format de sortie pour plus de détails).

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^5$), le nombre de cas de test.

Pour chaque cas de test, la première ligne contient quatre entiers positifs ou nuls $n$, $m$, $a$ et $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), représentant respectivement le nombre d'employés, le nombre de routes, le nombre d'heures de travail des managers et le nombre d'heures de travail des ouvriers.

La ligne suivante contient une chaîne de caractères de longueur $n$ composée uniquement de A et de B. Le $i$-ème caractère représente le type du $i$-ème employé.

Les $m$ lignes suivantes contiennent chacune deux entiers positifs ou nuls $u, v$ ($1 \le u, v \le n$), représentant une route.

Il est garanti que si les maisons des employés sont considérées comme des sommets et les routes comme des arêtes, le graphe n'a ni arêtes multiples ni boucles, et est connexe.

Il est garanti que la somme de $n$ et la somme de $m$ sur tous les cas de test ne dépassent pas $5 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez une ligne contenant $n$ entiers positifs ou nuls $s'_i$ ($0 \le s'_i \le 10^{18}$). Plus précisément, soit $s_i$ l'heure à laquelle le $i$-ème employé commence à travailler, alors $s_i = \frac{s'_i}{10^6}$. S'il existe plusieurs plannings optimaux qui minimisent le nombre de personnes insatisfaites, affichez l'un quelconque d'entre eux.

Exemple

Entrée 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

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