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

25/61

Solve/Submission

Ranking

# 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 MRoy Cpp14 0.82s
08 prateepm Cpp14 0.84s
09 Unsocial_A Cpp14 1.27s
10 moinul_shaon Cpp14 2.55s
11 mamun4122 Cpp14 2.59s
12 raihatneloy Cpp14 2.65s
13 sahedsohel Cpp14 2.70s
14 dipta007 Cpp14 3.01s
15 faisal47 Cpp14 3.18s
16 mahbubcseju Cpp14 3.47s
17 khatribiru Cpp14 3.57s
18 Matrix_code Cpp14 3.60s
19 darkprinx Cpp14 3.75s
20 akazad_cse13_ruet Cpp14 3.79s
21 Foyaz05 Cpp14 3.84s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support