How to optimize my code (CSES Hamiltonian Flights)

Revision en4, by Polyn0mial, 2022-07-01 12:23:19

Link to the problem I use bottom up DP, where $$$dp[\text{mask of visited vertices}][\text{ending vertex}]$$$. I'm pretty sure my time complexity is $$$O(N \cdot 2^N + 2^N \cdot N^2)$$$ however it gives TLE. Are there any way to optimize my code, and what's the reason for TLE (probably big constant factor?)

My code
Tags dp, #hamiltonian-path, graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Polyn0mial 2022-07-01 12:23:19 0 Tiny change: '}\n\n~~~~~\n\n\n</sp' -> '}\n\n~~~~~ \n\n\n</sp'
en3 English Polyn0mial 2022-07-01 10:21:28 63 (published)
en2 English Polyn0mial 2022-07-01 10:18:47 1050
en1 English Polyn0mial 2022-07-01 10:15:25 216 Initial revision (saved to drafts)