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 avwl017 Cpp14 0.31s
03 Morass Cpp14 0.33s
04 monir769 Cpp14 0.47s
05 Robbinb1993 Cpp 0.59s
06 tariqiitju Cpp14 0.80s
07 dhalachian Python3 0.81s
08 MRoy Cpp14 0.82s
09 BungakuShoujo Cpp14 0.83s
10 prateepm Cpp14 0.84s
11 Peregrine_Falcon Cpp14 0.97s
12 mesuyashky Cpp14 1.02s
13 amstan Cpp14 1.23s
14 Unsocial_A Cpp14 1.27s
15 Toirov_Sadi Cpp14 1.45s
16 moinul_shaon Cpp14 2.55s
17 mamun4122 Cpp14 2.59s
18 raihatneloy Cpp14 2.65s
19 sahedsohel Cpp14 2.70s
20 dipta007 Cpp14 3.01s
21 faisal47 Cpp14 3.18s
22 mahbubcseju Cpp14 3.47s
23 khatribiru Cpp14 3.57s
24 Matrix_code Cpp14 3.60s
25 darkprinx Cpp14 3.75s
26 akazad_cse13_ruet Cpp14 3.79s
27 Foyaz05 Cpp14 3.84s

Your feedback is our precious!

Or call +88 02 9853138 for support