Submission #1175786


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int,int> p;

int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};

#define MAX_N 20

int N, M;
bool edge[MAX_N][MAX_N];
ll dp[1 << MAX_N];
int main(){
    ios::sync_with_stdio(false);
    cin >> N >> M;
    REP(i, M) {
        int x, y;
        cin >> x >> y;
        x--;y--;
        edge[x][y] = true;
    }
    
    dp[0] = 1;
    REP(i, 1 << N) {
        REP(j, N) if ( !( 1 & (i >> j)) ) {
            bool isOk = true;
            REP(k, N) if ( 1 & (i >> k) ) {
                if (edge[j][k]) isOk = false;
            }
            if (isOk) dp[i + (1 << j)] += dp[i];
        }
    }
    
    cout << dp[int(1 << N)-1] << endl;
    
    return 0;
}

Submission Info

Submission Time
Task D - 徒競走
User yush1ga
Language C++14 (GCC 5.4.1)
Score 100
Code Size 952 Byte
Status AC
Exec Time 25 ms
Memory 768 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 3
AC × 15
AC × 32
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt
Subtask1 0_00.txt, 0_01.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
All 0_00.txt, 0_01.txt, 0_02.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, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.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 24 ms 768 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 1 ms 256 KB
1_02.txt AC 1 ms 256 KB
1_03.txt AC 1 ms 256 KB
1_04.txt AC 1 ms 256 KB
1_05.txt AC 1 ms 256 KB
1_06.txt AC 1 ms 256 KB
1_07.txt AC 1 ms 256 KB
1_08.txt AC 1 ms 256 KB
1_09.txt AC 1 ms 256 KB
1_10.txt AC 1 ms 256 KB
1_11.txt AC 1 ms 256 KB
1_12.txt AC 1 ms 256 KB
2_00.txt AC 24 ms 768 KB
2_01.txt AC 24 ms 768 KB
2_02.txt AC 24 ms 768 KB
2_03.txt AC 24 ms 768 KB
2_04.txt AC 12 ms 512 KB
2_05.txt AC 12 ms 512 KB
2_06.txt AC 12 ms 512 KB
2_07.txt AC 12 ms 512 KB
2_08.txt AC 25 ms 768 KB
2_09.txt AC 25 ms 768 KB
2_10.txt AC 25 ms 768 KB
2_11.txt AC 24 ms 768 KB
2_12.txt AC 25 ms 768 KB
2_13.txt AC 25 ms 768 KB
2_14.txt AC 25 ms 768 KB
2_15.txt AC 25 ms 768 KB