Submission #405644

#	Time	Username	Problem	Language	Result	Execution time	Memory
405644		Falcon	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	2157 ms	7620 KiB

amusementpark

#include <bits/stdc++.h>

#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};

array<int, 1 << 18> popcnt;
array<int, 1 << 18> lg;

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

    int j, sources;
    long long 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)] + popcnt[adj[j] & mask];

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

                if(popcnt[sources] & 1)
                    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;
    if(dp_c.back() < 0) dp_c.back() += mod;

    return make_pair(int(dp_c.back()), int(dp_s.back()));
}

vector<int> generate_adj(const vector<int>& adj, int mask) {
    vector<int> adj2(popcnt[mask]);
    vector<int> v;
    rep(i, int(adj.size())) if(mask & (1 << i)) v.push_back(i);
    
    rep(i, popcnt[mask]) rep(j, popcnt[mask])
        if(adj[v[i]] & (1 << v[j]))
            adj2[i] |= 1 << j;

    return adj2;
}

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

    rep(i, 1 << 18) popcnt[i] = __builtin_popcount(i);

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

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

    int vis{};
    long long p{1}, ans{};
    auto update_component = [&](int v) {
        int mask{};
        stack<int> s;
        s.push(v); mask |= 1 << v;
        while(!s.empty()) {
            int a = s.top(); s.pop();
            rep(u, n) {
                if(mask & (1 << u)) continue;
                if((adj[u] & (1 << a)) || (adj[a] & (1 << u)))
                    mask |= 1 << u, s.push(u);
            }
        }

        int cnt, sum;
        tie(cnt, sum) = solve_for(generate_adj(adj, mask));
        ans = (ans * cnt % mod + p * sum % mod) % mod;
        p = (p * cnt) % mod;

        vis |= mask;
    };

    rep(i, n)
        if(!(vis & (1 << i)))
            update_component(i);

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

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37