DCP-79: A Song of Ice and Fire Back to All Problems

Medium Graph Theory > Cycles/Topological Sorting/Strongly Connected Component

All the houses of Westeros have prepared themselves for the war. Some houses have alliance with other houses and some have alliance with none. Alliance between two houses is not both way. That means if house Tarley have their alliance with house Tyrell, then Tyrells can’t have alliance with Tarleys. It doesn’t make any sense! But since Bran is messing with the past nowadays, all have gone mad. ------ Given names of n houses, and m alliances between them we need to know how many camps can be formed. A camp consists of one or more houses. Only condition is the houses need to have alliance dependency with every other houses of the camp. If house Stark have their alliance with house Arryn, then Starks have alliance dependency with Arryns. If Arryns have their alliance with house Tully, then Arryns have alliance dependency with house Tully and Starks also have alliance dependency with house Tully. Now if house Tullys have alliance with the Starks, Tullys will have alliance dependency with Stark. Since Arryns already have alliance dependency on the Tullys, they will also have alliance dependency with the Starks. Since all houses now have alliance dependency with each other, they can form a camp. ------ After getting the camps, we need to find if there exists such a camp which has more member houses than rest of the camps combined. If such case occurs then that large camp will make the other camps join their forces and fight the White Walkers. Otherwise no one will listen to anyone and fight will continue. And they will be doomed. ------ Input: ------ First line of the input is the test case number **T.( 1 <= T <= 14)**. Next T set of lines each have two integers **n ( 1 <= n <= 100000 )** and **m ( 1 <= m <= min(100000, n*(n-1)/2 ))** followed by m lines which contain 2 strings **u, v ( 1 <= |u|,|v| <= 10 ).** It means house u has alliance with house v. String u, v consists only of lowercase english letter. ---------- String u, v consists only of lowercase English letter. Output: ------- If no camp has more members than rest of the houses, output “**Doomed**.”. Otherwise output “**Fight the white walkers.**” Sample Input ------------ 3 6 6 Stark Tully Arryn Stark Tully Arryn Bolton Lannister Lannister Tyrell Tyrell Bolton 6 3 Stark Tully Arryn Stark Tully Arryn 5 3 Stark Tully Arryn Stark Tully Arryn Sample Output ------------- Doomed. Doomed. Fight the white walkers.

Problem Setter:

Mahir Kabir

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 2.00
C++ 2.00
C++14 2.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats




# User Language Timing
01 feodorv C 0.09s
02 Morass Cpp14 0.33s
03 Robbinb1993 Cpp 0.59s
04 tariqiitju Cpp14 0.80s
05 MRoy Cpp14 0.82s
06 prateepm Cpp14 0.84s
07 moinul_shaon Cpp14 2.55s
08 mamun4122 Cpp14 2.59s
09 raihatneloy Cpp14 2.65s
10 sahedsohel Cpp14 2.70s
11 dipta007 Cpp14 3.01s
12 faisal47 Cpp14 3.18s
13 mahbubcseju Cpp14 3.47s
14 khatribiru Cpp14 3.57s
15 Matrix_code Cpp14 3.60s
16 darkprinx Cpp14 3.75s
17 akazad_cse13_ruet Cpp14 3.79s
18 Foyaz05 Cpp14 3.84s

Your feedback is our precious!

Or call +88 02 9853138 for support