oj.uz

Submission #439167

# Submission time Handle Problem Language Result Execution time Memory
439167 2021-06-29T10:57:30 Z prvocislo Amusement Park (CEOI19_amusementpark) C++17
0 / 100
 1 ms 204 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll mod = 998244353; // staci ho pouzit len raz, na konci
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> e(n);
    for (int i = 0, a, b; i < m; i++) 
    {
        cin >> a >> b;
        a--, b--;
        e[a] |= (1 << b);
        e[b] |= (1 << a);
    }
    vector<map<int, ll> > dp(1 << n); // dp[A][B]
    dp[0][(1 << n) - 1] = 1;
    for (int a = 0; a < (1 << n); a++)
    {
        for (const pair<int, ll> &i : dp[a])
        {
            int b = i.first; ll val = i.second;
            for (int c = 0; c < n; c++)
            {
                if (!((1 << c)&b)) continue;
                int nwa = a|(1 << c);
                int bad = ((1 << (c + 1))-1)&b;
                int in0 = (e[c] ^ a);
                int nwb = (b ^ bad) | in0;
                dp[nwa][nwb] += dp[a][b];
            }
        }
    }
    cout << (dp[(1 << n) - 1][0] * (ll)m / 2ll) % mod << "\n";
    return 0;
}

Compilation message

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:26:33: warning: unused variable 'val' [-Wunused-variable]
   26 |             int b = i.first; ll val = i.second;
      |                                 ^~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -