Submission #1498861


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int main() {
    //ifstream cin("f.in");

    int n, m; cin >> n >> m; 
    
    vector<vector<int>> mat(n, vector<int> (n, 0));
    vector<int> b(n, 0);

    for(int i = 0; i < m; ++i) {
        int x, y; cin >> x >> y;
        x -= 1, y -= 1;
        mat[x][y] = 1;
        b[x] |= (1 << y);
    }
    
    auto add = [&] (int &a, int b) {
        a += b;
        while(a >= MOD) {
            a -= MOD;
        }
        while(a < 0) {
            a += MOD;
        }
    };

    vector<vector<int>> dp(16, vector<int> ((1 << n), 0));
    vector<int> set_bits((1 << 15), 0);
    
    for(int i = 1; i < (1 << 15); ++i) {
        set_bits[i] = set_bits[i >> 1] + (i & 1);
    }

    for(int mask = 0; mask < (1 << n); ++mask) {
        int ways = 1;
        if((mask & 1) and (mask & 2))
            continue;
        for(int i = 0; i < n; ++i) {
            if((1 << i) & mask)
                continue;
            int who = set_bits[(b[i] & mask)];
            ways = 1LL * ways * ((1 << who) - 1) % MOD;
        }

        for(int i = 0; i < n; ++i) {
            if((1 << i) & mask) {
                int many = set_bits[b[i] & ((1 << n) - mask)];
                ways = 1LL * ways * ((1 << many)) % MOD;
            }
        }

        dp[0][mask] = ways;
    }

    for(int nimber = 1; nimber < 16; ++nimber) {
        for(int mask = 0; mask < (1 << n); ++mask) {
            for(int sub = mask - 1; sub > 0; sub = ((sub - 1) & mask)) {
                if((sub & 1) and (sub & 2))
                    continue;
                if(dp[nimber - 1][mask - sub] == 0)
                    continue;

                int ways = 1;
                for(int i = 0; i < n; ++i) {
                    if((1 << i) & mask)
                        continue;
                    int who = set_bits[(b[i] & sub)];
                    ways = 1LL * ways * ((1 << who) - 1) % MOD;
                    if(ways == 0) {
                        break;
                    }
                }
                
                if(ways == 0) {
                    continue;
                }

                for(int i = 0; i < n; ++i) {
                    if((1 << i) & sub) {
                        int many = set_bits[b[i] & ((1 << n) - mask)];
                        ways = 1LL * ways * (1 << many) % MOD;
                    }
                }

                int prv = dp[nimber - 1][mask - sub];
                add(dp[nimber][mask], 1LL * prv * ways % MOD);
            }
        }
    }

    int ans = 0;
    for(int nimber = 1; nimber < 16; ++nimber)
        add(ans, dp[nimber][(1 << n) - 1]);

    cout << ans << "\n";
}

Submission Info

Submission Time
Task F - Games on DAG
User mcalancea
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 2790 Byte
Status AC
Exec Time 627 ms
Memory 2556 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1600 / 1600
Status
AC × 4
AC × 40
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt
Case Name Status Exec Time Memory
0_00.txt AC 1 ms 384 KB
0_01.txt AC 1 ms 384 KB
0_02.txt AC 1 ms 384 KB
0_03.txt AC 1 ms 384 KB
1_00.txt AC 1 ms 384 KB
1_01.txt AC 291 ms 2432 KB
1_02.txt AC 291 ms 2432 KB
1_03.txt AC 627 ms 2556 KB
1_04.txt AC 598 ms 2432 KB
1_05.txt AC 627 ms 2432 KB
1_06.txt AC 400 ms 2432 KB
1_07.txt AC 512 ms 2432 KB
1_08.txt AC 627 ms 2432 KB
1_09.txt AC 575 ms 2432 KB
1_10.txt AC 596 ms 2432 KB
1_11.txt AC 497 ms 2432 KB
1_12.txt AC 609 ms 2432 KB
1_13.txt AC 614 ms 2432 KB
1_14.txt AC 622 ms 2432 KB
1_15.txt AC 525 ms 2432 KB
1_16.txt AC 491 ms 2432 KB
1_17.txt AC 626 ms 2432 KB
1_18.txt AC 380 ms 2432 KB
1_19.txt AC 623 ms 2432 KB
1_20.txt AC 292 ms 2432 KB
1_21.txt AC 4 ms 384 KB
1_22.txt AC 326 ms 2432 KB
1_23.txt AC 357 ms 2432 KB
1_24.txt AC 100 ms 1408 KB
1_25.txt AC 2 ms 384 KB
1_26.txt AC 441 ms 2432 KB
1_27.txt AC 14 ms 640 KB
1_28.txt AC 292 ms 2432 KB
1_29.txt AC 66 ms 896 KB
1_30.txt AC 13 ms 640 KB
1_31.txt AC 543 ms 2432 KB
1_32.txt AC 62 ms 896 KB
1_33.txt AC 14 ms 640 KB
1_34.txt AC 112 ms 1408 KB
1_35.txt AC 58 ms 896 KB