How to optimize my code (CSES Hamiltonian Flights)
Difference between en2 and en3, changed 63 character(s)
[Link to the problem](https://cses.fi/problemset/task/1690)↵
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?)

<spoiler summary="My code">↵

~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

const int M = 1e9 + 7;↵

const int N = 20;↵

int dp[1 << N][N];↵

int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
int n, m;↵
cin >> n >> m;↵
vector<tuple<int, int, int>> edges(m);↵
for(int i = 0; i < m; ++i) {↵
int u, v;↵
cin >> u >> v;↵
--u, --v;↵
edges[i] = {u, v, (1 << u) | (1 << v)};↵
}↵
vector<pair<int, int>> masks;↵
for(int i = 0; i < (1 << n); ++i) {↵
int j = __builtin_popcount(i);↵
if(j >= 2) {↵
masks.emplace_back(j, i);↵
}↵
}↵
sort(masks.begin(), masks.end());↵
dp[1][0] = 1;↵
for(int id = 0; id < (int) masks.size(); ++id) {↵
int mask = masks[id].second;↵
for(auto& [u, v, c] : edges) {↵
if((mask & c) == c) {↵
dp[mask][v] = (dp[mask][v] + dp[mask ^ (1 << v)][u]) % M;↵
}↵
}↵
}↵
cout << dp[(1 << n) - 1][n - 1] << "\n";↵
return 0;↵
}↵

~~~~~↵


</spoiler>↵

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)