Root of the tree can be determined by the minimum/maximum value node according to the parity of the number of vertices of the tree.
My approach was to run DFS on the graph to seperate its connected components out. Then, on each connected component run a DFS to determine its strength.
strength_even = strength of even sized connected components
strength_odd = strength of odd sized connected components
Print strength_even and strength_odd
This gave AC(100 pts) on pretests. Hope it passes system tests.
cutoff will probably be 200 for classes 10,11 and 12 and 132/115 for classes 9 and below
2 Likes
No, it didn’t give TLE for my code. I ran 2DFS only. Maybe your code was long.
For the first problem. I first took the inputs of all the connections, simultaneously making a structure I defined “group” which had variables for total employees, minimum_val employee, and max_val employee. As taking the inputs, I would merge 2 groups if both the employees already belonged to some group. After this, if the number of employees was even, I would start with the minimum employee, I would push it to a queue, followed by all it’s subordinates(If I know it’s on the top, all others are its subordinates, and with this same logic, I can know the manager of each employee, so I can know which employees are the subordinates and which is the manager. Then, I would run a BFS, and for each level i would multiply the total employees on that level with the value 1 for lev. 1, 2 for lev. 2 and so on.
this gave me AC for the first sub-task, AC for the first, second and last test cases for the second sub-task. One thing I noticed was that except for the second test case of the second sub-task, all the ACs I got were where there were only either odd or even groups. I didn’t even get TLE for the other cases, WA. I know this is pretty big, but could someone tell me what I did wrong here?
does that make a difference?
That can’t possible be true. I literally spent over an hour trying to optimise my code which did exactly that:
For each component, 1 DFS to find root node and type of department. 1 DFS to find strength with respect to this root nodes.
Net result = 2 DFS for each component of the graph.
I even went on to replace all my array indices with pointers, use faster I/O in C++ and use global variables to prevent re-declaration time.
Bottom line is - My code was optimised to the absolute limits and using the same logic as you say you have used, it gave a TLE on cases 5 and 6 of the second subtask.
What’s even funnier is that when I ran the code on my local machine and timed it using the Linux time command, sub tasks 5 and 6 ran in around 1.7-1.8 seconds on an average.
@shlok_1933, I think you said your code too gave TLE in 2 subtasks right? Did you use the same logic?
I feel terrible because if I could have used that one hour on the second question, I too could have got a 200. I’ve seen the second question before too, I think something similar came in INMO 2018 if I’m not wrong ?
@aryansanghi How did you get your program to AC in the first question ? There has to have been some difference in logic right ?
I was also for some reason getting a TLE in the first problem on test cases 5 and 6. I was running a simple DFS and a BFS. The code was pretty short and I wasted a lot of time on optimizing my code. I changed and removed every redundant thing I could find. What really surprised me was the uncertainty of the issue. I submitted my code once, got a TLE on 4 test cases, literally submitted the same exact code and got a TLE on only 2 test cases (and AC on the rest) and this was pretty random-ish. I met other people who used 2 DFS and 1 BFS and for some reason their code passed the test cases. What can be the issue? My computer’s internet went down for a while (although the staff ficed it in no time) but can this be due to that? idk I wasted a lot of time on the first problem trying to figure it out and … idk I am just sad and disappointed.
1 Like
Send code please
I first did the graph one with dfs and as I had completed the paper in half time I even did with bfs. I got didn’t get tle even once…its highly likely there is some line in your code like redeclaring arrays or something like that cz of which you got tle.
and also logic is same run bfs/dfs two time once to calculate roots and then again to calculate sum of levels.
I did with bfs twice aswell.
@tush_chen i guess you took an element again and again and ran same DFS many times as when it was included in an DFS, you didn’t do something to make sure that an element is not taken twice like by changing its colour. Therefore it ran good in 1st subtask as there was only 1 department but failed in multiple one. If you didn’t do this mistake, please send me an approximate code what you wrote, I’ll try my best to see why it’s giving TLE. Or maybe you used ‘endl’ instead of “\n”.
@kshitij_789 Even finished 1st question and the 1st and 2nd subtask of 2nd question within 1 hour. But i wasn’t able to figure out the 3rd subtask of 2nd question. Such a fool i am.
Same lol 
It happens with both of us many a times, i mean coincidence
BTW, I used 1 DFS to determine the the number of departments and people in each department and 1 DFS to find strength of each department. Node is automatically determined by the number of members in each department. I hope it helps. @tush_chen @shlok_1933
1 Like
No that’s exactly what I used, just 1 DFS call to figure out the root node and the type of team it would form. Then, another DFS call to figure out the strength of the team.
Also, what you suggested wouldn’t have happened because my first DFS call ran using a Boolean visited array, so the number of DFS calls would only be equal to the number of components in the graph.
My second DFS call ran by passing a node and it’s parent as arguments to a function.
Well, @anon95832944, I don’t remember my INOI account credentials so when the problems are uploaded onto INOI prac, I’ll solve it the exact same way and send the code here.
@kshitij_789, as I said before, I spent nearly an hour optimizing my code, it’s not possible that I would have left out redundant array declarations.
Anyways, when the problems come out on codechef, I’ll send the code here. It’ll be interesting to find out the reason for this anomalous behavior.
1 Like
I feel you man, sometimes we can try do everything right and stuff still goes wrong 
Some people in my center were also talking about how they implemented 2 DFS followed by 1 BFS and that code got a complete AC, so I was and still am equally as stupefied as you are.
I took care of that, which is why I got WA, no TLE errors, it is so weird I couldn’t find any error in my code at all, and if that had worked, could’ve easily attempted other questions
I used the exact sams node logic, and that is why my code ran on many cases, could it be that it was a memory issue and the system said (WA), isn’t there an error with a different name for a memory issue? Wrong answer is pretty misleading…