Submission #405519

#	Time	Username	Problem	Language	Result	Execution time	Memory
405519		Falcon	Amusement Park (CEOI19_amusementpark)	C++17	63 / 100	3060 ms	22204 KiB

amusementpark

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

class Modular {
    int value;
    
public:
    constexpr static int mod{998244353};

    Modular(long long x = 0) {
        value = (int)((x % mod + mod) % mod);
    }

    inline Modular& operator +=(Modular x) {
        value += x.value;
        if(value >= mod) value -= mod;
        return *this;
    }

    inline Modular& operator -=(Modular x) {
        value -= x.value;
        if(value < 0) value += mod;
        return *this;
    }

    inline Modular& operator *=(Modular x) {
        value = int((long long)x.value * value % mod);
        return *this;
    }
    
    // TODO : Make this Extended Euclid to handle composite moduli.
    inline Modular& operator /=(Modular x) {
        return *this *= x.pow(-1);
    }

    inline Modular operator -() const {
        return Modular(-value);
    }

    inline Modular& operator ++() {
        return *this += 1;
    }

    inline Modular& operator --() {
        return *this -= 1;
    }

    inline Modular operator ++(int) {
        Modular t{*this};
        *this += 1;
        return t;
    }

    inline Modular operator --(int) {
        Modular t{*this};
        *this -= 1;
        return t;
    }

    Modular pow(long long n) const { 
        while(n < 0) n += mod - 1;
        Modular v(1), a(value);
        for(; n; a *= a, n >>= 1)
            if(n & 1) v *= a;
        return v;
    }

    inline Modular operator +(Modular x) const {
        return x += *this;
    }

    inline Modular operator -(Modular x) const {
        return *this + (-x);
    }

    inline Modular operator *(Modular x) const {
        return x *= *this;
    }

    inline Modular operator /(Modular x) const {
        return (*this) * x.pow(-1);
    } 

    inline bool operator ==(Modular x) const {
        return value == x.value;
    }

    inline bool operator !=(Modular x) const {
        return value != x.value;
    }

    inline explicit operator int() const {
        return value;
    }

    Modular fact() const { 
        Modular x(1);
        for(int i = 1; i <= value; ++i) x *= i;
        return x;
    }

    friend ostream& operator <<(ostream& os, Modular x) {
        return os << x.value;
    }

    friend istream& operator >>(istream& is, Modular& x) {
        is >> x.value; x.value %= mod; return is;
    }

    friend string to_string(Modular x) {
        return std::to_string(int(x));
    }
};


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

    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<bool> is_independent(1 << n);
    rep(mask, 1 << n) {
        is_independent[mask] = true;        
        rep(i, n) if(mask & (1 << i))
            rep(j, n)
                if(adj[i][j] && (mask & (1 << j)))
                    is_independent[mask] = false;
    }
    
    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];  
        }
            
    /* auto partial_cost = [&](int mask, int sources) {
        int c{};
        rep(i, n)
            if(sources & (1 << i))
                c += single_cost[i][mask];
        return c;
    };*/

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

    vector<Modular> dp_s(1 << n), dp_c(1 << n); dp_c[0] = 1;
    vector<int> partial_cost(1 << n);
    rep1(mask, (1 << n) - 1) {
        for(int sources{mask}; ; sources = (sources - 1) & mask) {
            debug(sources);
            if(sources == mask) continue;
            sources = mask - sources;
            int j = __lg(sources);
            partial_cost[sources] =
                partial_cost[sources - (1 << j)] + single_cost[j][mask];
            if(is_independent[sources]) {
                Modular t_s{dp_s[mask ^ sources] + 
                    dp_c[mask ^ sources] * partial_cost[sources]};
                dp_s[mask] += parity[sources] ? -t_s : t_s;

                Modular t_c{dp_c[mask ^ sources]};
                dp_c[mask] += parity[sources] ? -t_c : t_c;
            }
            sources = mask - sources;
            debug(sources);
            if(sources == 0) break;
        }
        for(int sources{mask}; sources > 0; sources = (sources - 1) & mask)
            partial_cost[sources] = 0;

    }

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

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
amusementpark.cpp:205:13: note: in expansion of macro 'debug'
  205 |             debug(sources);
      |             ^~~~~
amusementpark.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
amusementpark.cpp:220:13: note: in expansion of macro 'debug'
  220 |             debug(sources);
      |             ^~~~~

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