NEED HELP IN BASIC GRAPH QUESTION - FIRESC

#1

Hello guys.
I have recently begun learning about graph theory concepts and I want to know how I could improve my solution because my current solution gives TLE.

How can I improve my memory and time requirements?
Here is the link: https://www.codechef.com/viewsolution/25912599
Question: https://www.codechef.com/problems/FIRESC

1 Like
#2

https://www.codechef.com/viewsolution/24471542
This is my solution

#3

how can we store the adjacency list in a vector?

#4

I made up some changes in your code:

  1. Taking adjacency list by reference, not creating a new one each time, that makes the code O(nm) (that’s why the TLE).
  2. After step 1, it got WA because of overflow of captains%MOD * num%MOD since both captains and num can be up to 10^5 and 10^{10} doesn’t fit in a signed 32-bit integer.

Accepted solution: https://www.codechef.com/viewsolution/25914089

1 Like
#5

So TLE can also happen when memory exceeds limit?

1 Like
#6

The TLE is caused because the program creates a complete new memory allocation for the adjacency list each time the DFS is called (which is O(|E| + |V|) each time, making the whole program to run in O(|V|(|V|+|E|))). When used by reference, no new memory is needed so it doesn’t spend execution time in replicating the adjacency list :smile:

2 Likes
#7

thanks a lot. I learned 2 new things today :smiley:

1 Like