Submission #1368317


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,M;
int E[15];
ll dp[1<<15];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	while(M--) {
		cin>>x>>y;
		x--,y--;
		E[x] |= 1<<y;
	}
	
	dp[0]=1;
	for(int ST=1;ST<1<<N;ST++) {
		int U=((1<<N)-1)^ST;
		for(int S=ST-1; S>=0; S--) {
			S&=ST;
			int T=ST^S;
			if((T&3)==3) continue;
			
			ll mul=1;
			FOR(i,N) {
				if(T&(1<<i)) (mul *= 1<<__builtin_popcount(E[i]&U))%=mo;
				if(U&(1<<i)) (mul *= (1<<__builtin_popcount(E[i]&T))-1)%=mo;
			}
			(dp[ST] += mul*dp[S])%=mo;
		}
	}
	cout<<dp[(1<<N)-1]<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}

Submission Info

Submission Time
Task F - Games on DAG
User kmjp
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 1260 Byte
Status AC
Exec Time 2671 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 2613 ms 512 KB
1_02.txt AC 2666 ms 512 KB
1_03.txt AC 2597 ms 512 KB
1_04.txt AC 2668 ms 512 KB
1_05.txt AC 2597 ms 512 KB
1_06.txt AC 2614 ms 512 KB
1_07.txt AC 2583 ms 512 KB
1_08.txt AC 2616 ms 512 KB
1_09.txt AC 2596 ms 512 KB
1_10.txt AC 2584 ms 512 KB
1_11.txt AC 2587 ms 512 KB
1_12.txt AC 2612 ms 512 KB
1_13.txt AC 2612 ms 512 KB
1_14.txt AC 2595 ms 512 KB
1_15.txt AC 2583 ms 512 KB
1_16.txt AC 2671 ms 512 KB
1_17.txt AC 2613 ms 512 KB
1_18.txt AC 2595 ms 512 KB
1_19.txt AC 2613 ms 512 KB
1_20.txt AC 2663 ms 512 KB
1_21.txt AC 9 ms 256 KB
1_22.txt AC 2582 ms 512 KB
1_23.txt AC 2581 ms 512 KB
1_24.txt AC 814 ms 384 KB
1_25.txt AC 3 ms 256 KB
1_26.txt AC 2616 ms 512 KB
1_27.txt AC 81 ms 256 KB
1_28.txt AC 2666 ms 512 KB
1_29.txt AC 256 ms 384 KB
1_30.txt AC 83 ms 256 KB
1_31.txt AC 2669 ms 512 KB
1_32.txt AC 256 ms 384 KB
1_33.txt AC 80 ms 256 KB
1_34.txt AC 817 ms 384 KB
1_35.txt AC 256 ms 384 KB