Submission #1175790
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 | 949 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 |
|
|
|
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 | 25 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 |