Submission #889744


Source Code Expand

#include <iostream>
#include <cstdio>

#define reep(i,n,m) for(int i=(n);i<(m);i++)
#define rep(i,n) reep(i,0,n)

using namespace std;

typedef long long ll;

bool a[16][16];
ll dp[1<<16];
int N,M;


int main(){
	cin >> N >> M;

	rep(i,M){
		int x,y;
		cin >> x >> y;
		a[x-1][y-1] = true;
	}

	dp[0] = 1;
	rep(i,1<<N){
		rep(k,N){
			if((i&(1<<k)) == 0){
				continue;
			}
			bool flg=false;
			rep(j,N){
				if(j==k){
					continue;
				}
				if(i&(1<<j) && a[k][j]){
					flg=true;
					break;
				}
			}
			if(flg){
				continue;
			}
			dp[i] += dp[i-(1<<k)];
		}
	}

	cout << dp[(1<<N) - 1] << endl;
}

Submission Info

Submission Time
Task D - 徒競走
User otama_jaccy
Language C++14 (GCC 5.4.1)
Score 100
Code Size 656 Byte
Status AC
Exec Time 31 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 3 ms 256 KB
0_01.txt AC 3 ms 256 KB
0_02.txt AC 31 ms 768 KB
1_00.txt AC 3 ms 256 KB
1_01.txt AC 3 ms 256 KB
1_02.txt AC 3 ms 256 KB
1_03.txt AC 3 ms 256 KB
1_04.txt AC 3 ms 256 KB
1_05.txt AC 3 ms 256 KB
1_06.txt AC 3 ms 256 KB
1_07.txt AC 3 ms 256 KB
1_08.txt AC 3 ms 256 KB
1_09.txt AC 3 ms 256 KB
1_10.txt AC 3 ms 256 KB
1_11.txt AC 3 ms 256 KB
1_12.txt AC 3 ms 256 KB
2_00.txt AC 31 ms 768 KB
2_01.txt AC 23 ms 768 KB
2_02.txt AC 23 ms 768 KB
2_03.txt AC 24 ms 768 KB
2_04.txt AC 11 ms 512 KB
2_05.txt AC 8 ms 512 KB
2_06.txt AC 12 ms 512 KB
2_07.txt AC 8 ms 512 KB
2_08.txt AC 24 ms 768 KB
2_09.txt AC 19 ms 768 KB
2_10.txt AC 19 ms 768 KB
2_11.txt AC 11 ms 768 KB
2_12.txt AC 28 ms 768 KB
2_13.txt AC 26 ms 768 KB
2_14.txt AC 27 ms 768 KB
2_15.txt AC 28 ms 768 KB