Hmm, I’m getting a wrong answer but can’t seem see, why, some basic tests locally seem to pass, anyone have a some more test cases that I could run my code through?
I’m using n*n-1/2 for calculating first answer by checking sub-trees for all “1” nodes.
The second answer I’m counting all leaves with no open windows and subtracting from the number of nodes, with a special case being 1, which I return 0.
Or am I mis-understanding the 2nd question, i.e. there is still a draught even if the room has no openwindow as a long as it is on the path of rooms that have openWindows, even if those rooms are not direct neighbours? So they can be few nodes away?
I solved this problem using a DFS that returns a parameter which tells whether the current node is to be included or not for the answer of 2nd part of the question… The description of my solution is given here
Rubik’s answer is not n. As stated by @anton_lunyov in the contest “After solving the problem I could assert that draught is passing through the room if and only if this room lies on the path between two different rooms with open windows (regardless of whether it has open window or not). Regarding Furik question, it is clear enough: the pair of rooms should be counted if and only if they are connected and both have open windows.”
@sambuddha - You did everything right … the only problem(the same i had) is that we forgot to explicit typecast the count to long long which cost me around 20 WA’s … here’s your AC solution which i tried
just modified the tot_count
Thanks to