oj.uz

Submission #405595

# Submission time Handle Problem Language Result Execution time Memory
405595 2021-05-16T14:57:22 Z Falcon Amusement Park (CEOI19_amusementpark) C++17
42 / 100
 22 ms 2744 KB 
#include <vector>
#include <array>
#include <iostream>

#ifdef DEBUG
#include "debug.hpp"
#endif

using namespace std;

#define all(c)              (c).begin(), (c).end()
#define rall(c)             (c).rbegin(), (c).rend()
#define traverse(c, it)     for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N)           for(int i = 0; i < (N); ++i)
#define rrep(i, N)          for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N)          for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e)       for(int i = (s); i <= (e); ++i)

#ifdef DEBUG
#define debug(x...)         { \
                            ++dbg::depth; \
                            string dbg_vals = dbg::to_string(x); \
                            --dbg::depth; \
                            dbg::fprint(__func__, __LINE__, #x, dbg_vals); \
                            }

#define light_debug(x)      { \
                            dbg::light = true; \
                            dbg::dout << __func__ << ":" << __LINE__; \
                            dbg::dout << "  " << #x << " = " << x << endl; \
                            dbg::light = false; \
                            }

#else
#define debug(x...)         42
#define light_debug(x)      42
#endif


using ll = long long;

template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }


constexpr int mod{998244353};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    array<bool, 1 << 18> parity;
    rep(i, 1 << 18) parity[i] = __builtin_popcount(i) % 2 == 0;

    array<int, 1 << 18> lg;
    rep(i, 1 << 18) lg[i] = __lg(i);

    int n, m; cin >> n >> m;
    vector<vector<bool>> adj(n, vector<bool>(n));
    rep(i, m) {
        int u, v; cin >> u >> v; --u, --v;
        adj[u][v] = true;
    }

    vector<vector<int>> single_cost(n, vector<int>(1 << n));
    rep(i, n)
        rep1(mask, (1 << n) - 1) {
             single_cost[i][mask] = single_cost[i][mask - (1 << lg[mask])]
                 + adj[lg[mask]][i];  
        }

    vector<bool> is_independent(1 << n, true);
    rep1(mask, (1 << n) - 1) {
        rep(i, n) 
            if((mask & (1 << i)) && single_cost[i][mask] != 0) {
                is_independent[mask] = false;
                break;
            }
                
    }
            
    vector<int> dp_s(1 << n), dp_c(1 << n); dp_c[0] = 1;
    vector<int> partial_cost(1 << n);

    int j, sources;
    int t_s, t_c;
    rep1(mask, (1 << n) - 1) {
        for(sources = mask & (mask - 1); ; sources = (sources - 1) & mask) {
            sources = mask - sources;

            if(is_independent[sources]) {
                j = lg[sources];
                partial_cost[sources] =
                    partial_cost[sources - (1 << j)] + single_cost[j][mask];

                t_c = dp_c[mask ^ sources];
                t_s = dp_s[mask ^ sources] +
                    dp_c[mask ^ sources] * partial_cost[sources] % mod;

                if(parity[sources])
                    dp_s[mask] -= t_s, dp_c[mask] -= t_c;
                else
                    dp_s[mask] += t_s, dp_c[mask] += t_c;
            }

            sources = mask - sources;
            if(sources == 0) break;
        }

        dp_c[mask] %= mod;
        dp_s[mask] %= mod;
    }

    if(dp_s.back() < 0) dp_s.back() += mod;

    cout << dp_s.back()  << '\n';
    
    
    #ifdef DEBUG
    dbg::dout << "\nExecution time: "
              << clock() * 1000 / CLOCKS_PER_SEC 
              << "ms" << endl;
    #endif
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1484 KB Output is correct
2 Correct 3 ms 1484 KB Output is correct
3 Correct 3 ms 1484 KB Output is correct
4 Correct 5 ms 1484 KB Output is correct
5 Correct 5 ms 1588 KB Output is correct
6 Correct 3 ms 1484 KB Output is correct
7 Correct 3 ms 1484 KB Output is correct
8 Correct 3 ms 1484 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1484 KB Output is correct
2 Correct 3 ms 1484 KB Output is correct
3 Correct 3 ms 1484 KB Output is correct
4 Correct 5 ms 1484 KB Output is correct
5 Correct 5 ms 1588 KB Output is correct
6 Correct 3 ms 1484 KB Output is correct
7 Correct 3 ms 1484 KB Output is correct
8 Correct 3 ms 1484 KB Output is correct
9 Correct 3 ms 1484 KB Output is correct
10 Correct 4 ms 1588 KB Output is correct
11 Correct 3 ms 1592 KB Output is correct
12 Correct 3 ms 1592 KB Output is correct
13 Correct 3 ms 1592 KB Output is correct
14 Correct 3 ms 1592 KB Output is correct
15 Correct 3 ms 1596 KB Output is correct
16 Correct 3 ms 1484 KB Output is correct
17 Correct 3 ms 1484 KB Output is correct
18 Correct 3 ms 1484 KB Output is correct
19 Correct 3 ms 1484 KB Output is correct
20 Correct 4 ms 1484 KB Output is correct
21 Correct 3 ms 1484 KB Output is correct
22 Correct 3 ms 1484 KB Output is correct
23 Correct 3 ms 1592 KB Output is correct
24 Correct 3 ms 1484 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1484 KB Output is correct
2 Correct 3 ms 1484 KB Output is correct
3 Correct 3 ms 1484 KB Output is correct
4 Correct 5 ms 1484 KB Output is correct
5 Correct 5 ms 1588 KB Output is correct
6 Correct 3 ms 1484 KB Output is correct
7 Correct 3 ms 1484 KB Output is correct
8 Correct 3 ms 1484 KB Output is correct
9 Correct 3 ms 1484 KB Output is correct
10 Correct 4 ms 1588 KB Output is correct
11 Correct 3 ms 1592 KB Output is correct
12 Correct 3 ms 1592 KB Output is correct
13 Correct 3 ms 1592 KB Output is correct
14 Correct 3 ms 1592 KB Output is correct
15 Correct 3 ms 1596 KB Output is correct
16 Correct 3 ms 1484 KB Output is correct
17 Correct 3 ms 1484 KB Output is correct
18 Correct 3 ms 1484 KB Output is correct
19 Correct 3 ms 1484 KB Output is correct
20 Correct 4 ms 1484 KB Output is correct
21 Correct 3 ms 1484 KB Output is correct
22 Correct 3 ms 1484 KB Output is correct
23 Correct 3 ms 1592 KB Output is correct
24 Correct 3 ms 1484 KB Output is correct
25 Correct 3 ms 1484 KB Output is correct
26 Correct 3 ms 1484 KB Output is correct
27 Correct 3 ms 1484 KB Output is correct
28 Correct 3 ms 1588 KB Output is correct
29 Correct 4 ms 1484 KB Output is correct
30 Correct 4 ms 1568 KB Output is correct
31 Correct 3 ms 1484 KB Output is correct
32 Correct 3 ms 1484 KB Output is correct
33 Correct 4 ms 1484 KB Output is correct
34 Correct 6 ms 1588 KB Output is correct
35 Correct 4 ms 1484 KB Output is correct
36 Correct 3 ms 1484 KB Output is correct
37 Correct 3 ms 1592 KB Output is correct
38 Correct 3 ms 1484 KB Output is correct
39 Correct 3 ms 1592 KB Output is correct
40 Correct 3 ms 1612 KB Output is correct
41 Correct 4 ms 1612 KB Output is correct
42 Correct 4 ms 1616 KB Output is correct
43 Correct 3 ms 1612 KB Output is correct
44 Correct 6 ms 1612 KB Output is correct
45 Correct 5 ms 1592 KB Output is correct
46 Correct 6 ms 1612 KB Output is correct
47 Correct 4 ms 1612 KB Output is correct
48 Correct 5 ms 1596 KB Output is correct
49 Correct 5 ms 1584 KB Output is correct
50 Correct 5 ms 1612 KB Output is correct
51 Correct 4 ms 1584 KB Output is correct
52 Correct 5 ms 1592 KB Output is correct
53 Correct 3 ms 1612 KB Output is correct
54 Correct 3 ms 1592 KB Output is correct
55 Correct 4 ms 1612 KB Output is correct
56 Correct 5 ms 1592 KB Output is correct
57 Correct 5 ms 1612 KB Output is correct
58 Correct 3 ms 1612 KB Output is correct
59 Correct 3 ms 1612 KB Output is correct
60 Correct 3 ms 1584 KB Output is correct
61 Correct 4 ms 1612 KB Output is correct
62 Correct 5 ms 1612 KB Output is correct
63 Correct 3 ms 1588 KB Output is correct
64 Correct 5 ms 1612 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1484 KB Output is correct
2 Correct 3 ms 1484 KB Output is correct
3 Correct 3 ms 1484 KB Output is correct
4 Correct 5 ms 1484 KB Output is correct
5 Correct 5 ms 1588 KB Output is correct
6 Correct 3 ms 1484 KB Output is correct
7 Correct 3 ms 1484 KB Output is correct
8 Correct 3 ms 1484 KB Output is correct
9 Correct 3 ms 1484 KB Output is correct
10 Correct 4 ms 1588 KB Output is correct
11 Correct 3 ms 1592 KB Output is correct
12 Correct 3 ms 1592 KB Output is correct
13 Correct 3 ms 1592 KB Output is correct
14 Correct 3 ms 1592 KB Output is correct
15 Correct 3 ms 1596 KB Output is correct
16 Correct 3 ms 1484 KB Output is correct
17 Correct 3 ms 1484 KB Output is correct
18 Correct 3 ms 1484 KB Output is correct
19 Correct 3 ms 1484 KB Output is correct
20 Correct 4 ms 1484 KB Output is correct
21 Correct 3 ms 1484 KB Output is correct
22 Correct 3 ms 1484 KB Output is correct
23 Correct 3 ms 1592 KB Output is correct
24 Correct 3 ms 1484 KB Output is correct
25 Correct 3 ms 1484 KB Output is correct
26 Correct 3 ms 1484 KB Output is correct
27 Correct 3 ms 1484 KB Output is correct
28 Correct 3 ms 1588 KB Output is correct
29 Correct 4 ms 1484 KB Output is correct
30 Correct 4 ms 1568 KB Output is correct
31 Correct 3 ms 1484 KB Output is correct
32 Correct 3 ms 1484 KB Output is correct
33 Correct 4 ms 1484 KB Output is correct
34 Correct 6 ms 1588 KB Output is correct
35 Correct 4 ms 1484 KB Output is correct
36 Correct 3 ms 1484 KB Output is correct
37 Correct 3 ms 1592 KB Output is correct
38 Correct 3 ms 1484 KB Output is correct
39 Correct 3 ms 1592 KB Output is correct
40 Correct 3 ms 1612 KB Output is correct
41 Correct 4 ms 1612 KB Output is correct
42 Correct 4 ms 1616 KB Output is correct
43 Correct 3 ms 1612 KB Output is correct
44 Correct 6 ms 1612 KB Output is correct
45 Correct 5 ms 1592 KB Output is correct
46 Correct 6 ms 1612 KB Output is correct
47 Correct 4 ms 1612 KB Output is correct
48 Correct 5 ms 1596 KB Output is correct
49 Correct 5 ms 1584 KB Output is correct
50 Correct 5 ms 1612 KB Output is correct
51 Correct 4 ms 1584 KB Output is correct
52 Correct 5 ms 1592 KB Output is correct
53 Correct 3 ms 1612 KB Output is correct
54 Correct 3 ms 1592 KB Output is correct
55 Correct 4 ms 1612 KB Output is correct
56 Correct 5 ms 1592 KB Output is correct
57 Correct 5 ms 1612 KB Output is correct
58 Correct 3 ms 1612 KB Output is correct
59 Correct 3 ms 1612 KB Output is correct
60 Correct 3 ms 1584 KB Output is correct
61 Correct 4 ms 1612 KB Output is correct
62 Correct 5 ms 1612 KB Output is correct
63 Correct 3 ms 1588 KB Output is correct
64 Correct 5 ms 1612 KB Output is correct
65 Correct 18 ms 2744 KB Output is correct
66 Incorrect 22 ms 2636 KB Output isn't correct
67 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1484 KB Output is correct
2 Correct 3 ms 1484 KB Output is correct
3 Correct 3 ms 1484 KB Output is correct
4 Correct 5 ms 1484 KB Output is correct
5 Correct 5 ms 1588 KB Output is correct
6 Correct 3 ms 1484 KB Output is correct
7 Correct 3 ms 1484 KB Output is correct
8 Correct 3 ms 1484 KB Output is correct
9 Correct 3 ms 1484 KB Output is correct
10 Correct 4 ms 1588 KB Output is correct
11 Correct 3 ms 1592 KB Output is correct
12 Correct 3 ms 1592 KB Output is correct
13 Correct 3 ms 1592 KB Output is correct
14 Correct 3 ms 1592 KB Output is correct
15 Correct 3 ms 1596 KB Output is correct
16 Correct 3 ms 1484 KB Output is correct
17 Correct 3 ms 1484 KB Output is correct
18 Correct 3 ms 1484 KB Output is correct
19 Correct 3 ms 1484 KB Output is correct
20 Correct 4 ms 1484 KB Output is correct
21 Correct 3 ms 1484 KB Output is correct
22 Correct 3 ms 1484 KB Output is correct
23 Correct 3 ms 1592 KB Output is correct
24 Correct 3 ms 1484 KB Output is correct
25 Correct 3 ms 1484 KB Output is correct
26 Correct 3 ms 1484 KB Output is correct
27 Correct 3 ms 1484 KB Output is correct
28 Correct 3 ms 1588 KB Output is correct
29 Correct 4 ms 1484 KB Output is correct
30 Correct 4 ms 1568 KB Output is correct
31 Correct 3 ms 1484 KB Output is correct
32 Correct 3 ms 1484 KB Output is correct
33 Correct 4 ms 1484 KB Output is correct
34 Correct 6 ms 1588 KB Output is correct
35 Correct 4 ms 1484 KB Output is correct
36 Correct 3 ms 1484 KB Output is correct
37 Correct 3 ms 1592 KB Output is correct
38 Correct 3 ms 1484 KB Output is correct
39 Correct 3 ms 1592 KB Output is correct
40 Correct 3 ms 1612 KB Output is correct
41 Correct 4 ms 1612 KB Output is correct
42 Correct 4 ms 1616 KB Output is correct
43 Correct 3 ms 1612 KB Output is correct
44 Correct 6 ms 1612 KB Output is correct
45 Correct 5 ms 1592 KB Output is correct
46 Correct 6 ms 1612 KB Output is correct
47 Correct 4 ms 1612 KB Output is correct
48 Correct 5 ms 1596 KB Output is correct
49 Correct 5 ms 1584 KB Output is correct
50 Correct 5 ms 1612 KB Output is correct
51 Correct 4 ms 1584 KB Output is correct
52 Correct 5 ms 1592 KB Output is correct
53 Correct 3 ms 1612 KB Output is correct
54 Correct 3 ms 1592 KB Output is correct
55 Correct 4 ms 1612 KB Output is correct
56 Correct 5 ms 1592 KB Output is correct
57 Correct 5 ms 1612 KB Output is correct
58 Correct 3 ms 1612 KB Output is correct
59 Correct 3 ms 1612 KB Output is correct
60 Correct 3 ms 1584 KB Output is correct
61 Correct 4 ms 1612 KB Output is correct
62 Correct 5 ms 1612 KB Output is correct
63 Correct 3 ms 1588 KB Output is correct
64 Correct 5 ms 1612 KB Output is correct
65 Correct 18 ms 2744 KB Output is correct
66 Incorrect 22 ms 2636 KB Output isn't correct
67 Halted 0 ms 0 KB -