Submission #1608763


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int Mod = 1e9 + 7;

int x, y, mask, m0, m1, res, dp[1 << 15], n, m, i, cntb[1 << 15], go[20], ans = 1;
bool good[1 << 15];

void inm(int &x, int y)
{
    x = (long long) x * y % Mod;
}

void add(int &x, int y)
{
    x += y;
    if(x >= Mod) x -= Mod;
}

int main()
{
 //   freopen("input", "r", stdin);

    cin >> n >> m;
    for(i=1; i<=m; ++i)
    {
        cin >> x >> y;
        --x; --y;
        go[x] |= (1<<y);
        inm(ans, 2);
    }

    for(i = 0; i < (1<<n); ++i)
    {
        good[i] = ((i&3) == 3 || (i&3) == 0);
        cntb[i] = cntb[i>>1] + (i&1);
    }

    dp[0] = 1;
    for(mask = 1; mask < (1<<n); ++ mask)
    if(good[mask])
    {
        dp[mask] = 1;
        for(m1 = mask & (mask - 1); m1; m1 = mask & (m1 - 1))
        {
            m0 = mask ^ m1;
            if(!good[m0] || !good[m1]) continue;

            res = dp[m1];
            for(i=0; i<n; ++i)
                if(m0 & (1<<i))
                    inm(res, (1 << cntb[go[i] & m1]));
                else if(m1 & (1<<i))
                    inm(res, (1 << cntb[go[i] & m0]) - 1);
            add(dp[mask], res);
        }
    }

    add(ans, Mod - dp[mask-1]);
    cout << ans << '\n';

    return 0;
}

Submission Info

Submission Time
Task F - Games on DAG
User Alexa2001
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 1311 Byte
Status AC
Exec Time 388 ms
Memory 512 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 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
0_03.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 368 ms 512 KB
1_02.txt AC 368 ms 512 KB
1_03.txt AC 388 ms 512 KB
1_04.txt AC 386 ms 512 KB
1_05.txt AC 387 ms 512 KB
1_06.txt AC 381 ms 512 KB
1_07.txt AC 384 ms 512 KB
1_08.txt AC 387 ms 512 KB
1_09.txt AC 386 ms 512 KB
1_10.txt AC 385 ms 512 KB
1_11.txt AC 385 ms 512 KB
1_12.txt AC 387 ms 512 KB
1_13.txt AC 386 ms 512 KB
1_14.txt AC 387 ms 512 KB
1_15.txt AC 384 ms 512 KB
1_16.txt AC 383 ms 512 KB
1_17.txt AC 387 ms 512 KB
1_18.txt AC 379 ms 512 KB
1_19.txt AC 387 ms 512 KB
1_20.txt AC 368 ms 512 KB
1_21.txt AC 2 ms 256 KB
1_22.txt AC 368 ms 512 KB
1_23.txt AC 374 ms 512 KB
1_24.txt AC 122 ms 384 KB
1_25.txt AC 1 ms 256 KB
1_26.txt AC 385 ms 512 KB
1_27.txt AC 13 ms 256 KB
1_28.txt AC 368 ms 512 KB
1_29.txt AC 41 ms 384 KB
1_30.txt AC 13 ms 256 KB
1_31.txt AC 385 ms 512 KB
1_32.txt AC 41 ms 384 KB
1_33.txt AC 13 ms 256 KB
1_34.txt AC 122 ms 384 KB
1_35.txt AC 41 ms 384 KB