Problem S4: Painting Roads
Problem Description
Alanna, the mayor of Kitchener, has successfully improved the city’s road plan. However, a
travelling salesperson from the city of RedBlue complained that the roads are not colourful
enough. Alanna’s second job is to paint some of the roads.
Kitchener’s road plan can be represented as a collection of N intersections with M roads,
where the i-th road connects intersections ui and vi
. All roads are initially grey. Alanna
would like to paint some of the roads in red or blue such that the following condition is
satisfied:
• Whenever there is a grey road that connects ui and vi
, there is also a path of roads
from ui to vi such that the roads on the path alternate between red and blue, without
any of the roads on this path being grey.
To lower the city’s annual spending, Alanna would like to minimize the number of painted
roads. Can you help Alanna design a plan that meets all the requirements?
Input Specification
The first line contains two integers N and M (1 ≤ N, M ≤ 2 · 105
).
The i-th of the next M lines contains two integers ui and vi
, meaning that there exists a
road from intersection ui to intersection vi (1 ≤ ui
, vi ≤ N, ui ̸= vi).
There is at most one road between any unordered pair of intersections.
The following table shows how the available 15 marks are distributed:
Marks Additional Constraints
2 There is a road connecting intersection i with intersection i + 1 for all 1 ≤ i < N
(and possibly other roads).
3 We can reach any intersection from any other intersection, and N = M.
3 No road belongs to two or more simple cycles (see Definition below).
7 None
Definition: if we denote a road between intersections u and v as u ↔ v, then a simple cycle
is a sequence w1 ↔ w2 ↔ . . . ↔ wk ↔ w1 where k ≥ 3 and all wi are distinct.
Output Specification
Output a string of M characters, representing the paint plan. The i-th character should be
R if the i-th road is to be painted red, B if i-th road is to be painted blue, or G (for “grey”)
if the i-th road is to be left unpainted.
La version fran¸caise figure `a la suite de la version anglaise.
Remember that you must minimize the number of painted roads while satisfying the condition. If there are multiple possible such plans, output any of them.
Sample Input 1
5 7
1 2
2 4
5 2
4 5
4 3
1 3
1 4
Output for Sample Input 1
RGGRGRB
Explanation of Output for Sample Input 1
A diagram of the intersections along with a valid paint plan that minimizes the number of
painted roads is shown below. Note that the colours are shown on each road as R (red), B
(blue), or G (grey).
1 2
3 4 5
R
R B G2 G3
G5 R
All the unpainted roads satisfy the condition:
• The 2nd road, labelled G2, connects intersection 2 with intersection 4. The path
through intersections 2, 1, 4 alternates red, blue.
• The 3rd road, labelled G3, connects intersection 5 with intersection 2. The path
through intersections 5, 4, 1, 2 alternates red, blue, red.
• The 5th road, labelled G5, connects intersection 4 with intersection 3. The path
through intersections 4, 1, 3 alternates blue, red.
La version fran¸caise figure `a la suite de la version anglaise.
Sample Input 2
4 2
1 2
3 4
Output for Sample Input 2
BB
Explanation of Output for Sample Input 2
Note that it is possible for Kitchener to be disconnected.
La version fran¸caise figure `a la suite de la version anglaise.
Probl`eme S4 : Peindre les routes
Enonc´e du probl`eme ´
Alanna, la mairesse de Kitchener, a r´eussi `a am´eliorer le plan routier de la ville. Cependant,
un vendeur itin´erant de la ville de RougeBleu s’est plaint que les routes manquaient de
couleur. Par cons´equent, la nouvelle mission d’Alanna consiste `a peindre certaines des routes.
Le plan routier de Kitchener est compos´e de N intersections avec M routes, o`u la i
i`eme route
relie les intersections ui et vi
. Initialement, toutes les routes sont grises. Alanna aimerait
peindre certaines routes en rouge ou en bleu de mani`ere que la condition suivante soit
remplie :
— Pour toute route grise reliant ui `a vi
, il doit exister un itin´eraire de ui `a vi compos´e
de routes dont les couleurs alternent entre rouge et bleu, sans qu’aucune route de cet
itin´eraire ne soit grise.
Dans l’optique de limiter les d´epenses annuelles de la ville, Alanna souhaite minimiser le
nombre de routes `a peindre. Pouvez-vous aider Alanna `a concevoir un plan qui r´epond `a
toutes ces exigences ?
Pr´ecisions par rapport aux donn´ees d’entr´ee
La premi`ere ligne des donn´ees d’entr´ee doit contenir deux entiers N et M (1 ≤ N,
M ≤ 2 · 105
).
La i
i`eme ligne des M lignes suivantes doit contenir deux entiers ui et vi
, indiquant qu’il existe
une route reliant l’intersection ui `a l’intersection vi (1 ≤ ui
, vi ≤ N, ui ̸= vi).
Il existe au maximum une route entre chaque paire non ordonn´ee d’intersections.
Le tableau ci-dessous d´etaille la r´epartition des 15 points disponibles.
Points Contraintes additionnelles
2 Il existe une route reliant l’intersection i `a l’intersection i+1 pour tout 1 ≤ i < N
(et possiblement d’autres routes).
3 Il est possible de se rendre `a n’importe quelle intersection depuis une autre et
N = M.
3 Aucune route n’appartient `a deux ou plus cycles simples (voir la d´efinition cidessous).
7 Aucune
D´efinition : soit u ↔ v une route qui relie les intersections u et v. Un cycle simple est une
suite w1 ↔ w2 ↔ . . . ↔ wk ↔ w1, wi ´etant tous distincts et k ≥ 3.
English version appears before the French version
Pr´ecisions par rapport aux donn´ees de sortie
Les donn´ees de sortie devraient afficher une chaˆıne de M caract`eres, repr´esentant le plan de
peinture. Le i
i`eme caract`ere devrait ˆetre R si la i
i`eme route doit ˆetre peinte en rouge, B si la
i
i`eme route doit ˆetre peinte en bleu ou G (pour ≪ gris ≫) si la i
i`eme route ne doit pas ˆetre
peinte.
Il est imp´eratif de minimiser le nombre de routes `a peindre tout en remplissant la condition
´etablie. S’il existe plusieurs plans possibles, les donn´ees de sortie peuvent en afficher un
quelconque.
Donn´es d’entr´ee d’un 1er exemple
5 7
1 2
2 4
5 2
4 5
4 3
1 3
1 4
Donn´es de sortie du 1er exemple
RGGRGRB
Justification des donn´es de sortie du 1er exemple
La figure ci-dessous illustre les intersections ainsi qu’un plan de peinture qui minimise le
nombre de routes `a peindre. Les couleurs des routes sont repr´esent´ees par les lettres R
(rouge), B (bleu) ou G (gris).
1 2
3 4 5
R
R B G2 G3
G5 R
English version appears before the French version
Toutes les routes non peintes remplissent la condition :
— La 2e
route, soit la route G2, relie l’intersection 2 `a l’intersection 4. Les couleurs du
chemin passant par les intersections 2, 1, 4 alternent de la mani`ere suivante : rouge,
bleu.
— La 3e
route, soit la route G3, relie l’intersection 5 `a l’intersection 2. Les couleurs du
chemin passant par les intersections 5, 4, 1, 2 alternent de la mani`ere suivante : rouge,
bleu, rouge.
— La 5e
route, soit la route G5, relie l’intersection 4 `a l’intersection 3. Les couleurs du
chemin passant par les intersections 4, 1, 3 alternent de la mani`ere suivante : bleu,
rouge.
Donn´es d’entr´ee d’un 2e exemple
4 2
1 2
3 4
Donn´es de sortie du 2e exemple
BB
Justification des donn´es de sortie du 2e exemple
Remarquons qu’il est possible que Kitchener soit d´econnect´e.
English version appears before the French version
请加QQ：99515681  邮箱：99515681@qq.com   WX：codehelp