# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
806876 | PanosPask | Amusement Park (CEOI19_amusementpark) | C++14 | 1 ms | 304 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define CHECK_BIT(val, pos) (val & (1 << pos))
using namespace std;
const int MOD = (int)1e9 + 7;
typedef long long ll;
typedef pair<int, int> pi;
int N, M;
vector<vector<int>> adj_list;
// dp[s]: Total cost and total number of ways
vector<pi> dp;
void add(int& a, int b)
{
a += b;
if (a > MOD)
a -= MOD;
}
void add(pi& a, pi b)
{
add(a.f, b.f);
add(a.s, b.s);
}
int main(void)
{
scanf("%d %d", &N, &M);
adj_list.resize(N);
for (int i = 0; i < M; i++) {
int u, v;
scanf("%d %d", &u, &v);
u--; v--;
adj_list[u].pb(v);
}
dp.resize(1 << N);
dp[0] = mp(0, 1);
for (int i = 0; i < 1 << N; i++) {
for (int u = 0; u < N; u++) {
if (CHECK_BIT(i, u))
continue;
int res = dp[i].f;
int times = dp[i].s;
for (auto v : adj_list[u]) {
if (CHECK_BIT(i, v)) {
add(res, times);
}
}
add(dp[i ^ (1 << u)], mp(res, times));
}
}
printf("%d\n", dp[(1 << N) - 1].f);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |