Brush FireProblem code: FIRE |
All submissions for this problem are available.
Help! A brush fire has started near your house and you are the only one who can help extinguish it. The only tool you have at your disposal is a single fireproof barrier that can protect one bush at a time, provided the bush has not yet caught fire already. For simplicity, we will assume the flames spread according to the following discrete time model.
Initially, a single bush, say s, is on fire. You choose a bush, say k, to save. The flames then leap from s to every bush near s with the exception of bush k if it was near s. Say these new burning bushes form a set B. Bush s is then reduced to ashes and will never burn again. Now that the bushes in B are on fire, you may move the protective barrier from bush k to some other bush k'. The flames leap from bushes in B to every bush that has not yet burned (i.e. not s or in B) and is close enough to some bush in B except, perhaps, bush k'. Say this new set of burning bushes is B'. The bushes in set B are reduced to ashes and will never burn again. Now, you may move the protective barrier from k' to another bush to protect it from the flames that will spread from bushes in B' and so on. This process repeats until there are no more bushes on fire.
The bushes are arranged in a peculiar manner. Before the fire started, each bush was close enough to spread a fire to at most three other bushes. Moreover, the bush that was initially on fire is actually close enough to only at most two other bushes. It is understood that for any two bushes A and B, if bush A is close enough to bush B then bush B is also close enough to bush A. Finally, the graph underlying the "close enough" relation has no cycles.
For whatever reason, some of the bushes hold some sentimental value to you. For this reason, you want to save all of these bushes.
Input
The first line of the input contains a single integer T ≤ 40 indicating the number of test cases that will follow. Each test case begins with three integers n, s, and t satisfying 1 ≤ n ≤ 10,000 and both s and t are between 1 and n. Here, n is the number of bushes (indexed from 1 to n), s is the index of the bush that is initially on fire, and t is the number of bushes you want to save.
Following this, there are n lines describing the "close enough" relation. The i'th line starts with an integer 0 ≤ ci ≤ 3 meaning bush i is close enough to ci other bushes. The remaining ci integers on this line are the indices of the bushes that bush i is close to. As mentioned earlier, the input will be such that if bush i is close enough to bush j, then bush j is also close enough to bush i. Finally, we also guarantee that cs ≤ 2.
The last line of input for each test case consists of t distinct integers between 1 and n. These correspond to indices of bushes you want to save.
Test cases are separated by a single blank line (including a blank line preceding the first test case).
Output
For each test case, you are to output a single line consisting of either "yes" or "no", depending on whether or not it is possible to save all of the indicated bushes.
Example
Input: 3 3 1 2 2 2 3 1 1 1 1 2 3 3 1 1 2 2 3 1 1 1 1 2 7 1 3 2 2 3 3 1 4 5 3 1 6 7 1 2 1 2 1 3 1 3 4 5 7 Output: no yes yes
| Date: | 2010-06-07 |
| Time limit: | 3s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
feels like spraying petrol on
feels like spraying petrol on all these bushes . .
is the answer for the last
is the answer for the last testcase correct??
I think the last test case
I think the last test case should be a no.Can anyone explain?
At a time more than one bush
At a time more than one bush can burn ?
I can't understand the input.
I can't understand the input. Can somebody explain which part of the input corresponds to which paragraph in the problem description?
just want to confirm that in
just want to confirm that in the entire graph that forms there can not be a loop right?
yeah i also think that the
yeah i also think that the answer to last test case shud b no and my explanation is as follows:-
since in start 1 is burning and i hv to save 4,5,7 let it b i save 4..since 2,3 are in viscinity of 1..so dey will catch fire...nw i hv to save one among 5 and 7..let it b i save 5...nw 1,4,5 are in viscinity of 2 and 1,5,7 are in viscinity of 3...and hence dey will catch fire too..since is already burnt nd i hv saved 5 nd 4 ..thus 7 will catch fire..nd i wont b able to save it...so answer shud b no...correct me if m wrong.
can the admins please explain
can the admins please explain how the answer for the last case is "yes" ?
@manish: answer is correct
@manish: answer is correct since 1 is at fire so next to catch fire will be 2 and 3.... so i will save 2 so it wont catch fire and 3 will catch fire.... now next to catch fire will be 6 and 7 since i have to save 7 so i ll save 7... remember 4 and 5 are automatically saved when i saved 2....
sorry got it, it should be
sorry got it, it should be "yes"
Please help. Will the input
Please help. Will the input contain blank lines like the example input, i.e. empty line in the begining then 3 then another empty line and so on..
I am tired of the runtime error
The input description tells
The input description tells you exactly where blank lines occur.
"the graph underlying the
"the graph underlying the "close enough" relation has no cycles."
is it means that.
if
1->2,3
then
2->1,3 and 3->1,2 is not possible?
-> close to
"the graph underlying the
"the graph underlying the "close enough" relation has no cycles."
is it means that.
if
1->2,3
then
2->1,3 and 3->1,2 is not possible?
-> close to
i f there s no bush that you
i f there s no bush that you have to save, i.e. t = 0 then would t be mentioned
can some1 plz give a sample test case for t = 0
I am getting runtime error in reading t
ok t is between 1 and n, but
ok t is between 1 and n, but still i cant figure out why it is giving a runtime error on just reading t
any1 using python on this one?
I didn't get question
I didn't get question correctely can any one help me to understand it.
Thanking You...
NZEC! not again! :(
NZEC! not again! :(
NZEC! not again! :(
NZEC! not again! :(
@chandni - are you using
@chandni - are you using python?
no i am coding in java.
no i am coding in java.
What does this input for
What does this input for "close enough" relation means? : 2 2 3
@ Pankaj Upadhyaya: You are saving bushes 4,5 and 7 by saving bush 3 not bush 2.
Is this a Tree month ??? All
Is this a Tree month ???
All problems are involving bushes ,trees,leaves,graphs,cycles ,subtrees !!!!!!
@Lucky This is from the Input
@Lucky This is from the Input section -> " The i'th line starts with an integer 0 ≤ ci ≤ 3 meaning bush i is close enough to ci other bushes. The remaining ci integers on this line are the indices of the bushes that bush i is close to" ... which means since 2 2 3 is the first line, 1 has 2 bushes that it is close to, bushes with number 2 and 3.
Tired.....of TLE!!!can't make
Tired.....of TLE!!!can't make it better anymore...
Can ne1 provide a good test
Can ne1 provide a good test case...My answer for above testcases are correct..but it is showing wrong answer...
Thanks for clarifying.... gr8
Thanks for clarifying.... gr8 help
@Pankaj : You are right, you
@Pankaj : You are right, you saved the bushes... :P by saving 2
About the third test case :
About the third test case : you can save the nodes 4 and 5, by saving the node 2
.My answer for above
.My answer for above testcases . But getting wrong answer. Can anyone give me a good test case.
When will be ci zero?....
When will be ci zero?....
@Admin:- Now the contest is
@Admin:- Now the contest is over plz tell me where i went wrong... I tried all possible test cases and ended up with a WA.....
http://www.codechef.com/viewsolution/330462
NZEC! not
NZEC! not again!!!!!!!!!!!!!!!!!!!!!!!!!1
Can ne1 help.. How the ans to