[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>↵
↵
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
↵
<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>↵
↵