Submission #1362637
Source Code Expand
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,b[20][20],m,A[20],B[20][20],d[20],two[110000],ans;
const int mo=1e9+7;
void get(int k,int now,int way){
// cout<<"fa "<<k<<" "<<now<<" "<<way<<endl;
if (k==2){
// for (int i=1;i<=n;i++) cout<<A[i]<<" "; cout<<endl;
// for (int i=0;i<=n;i++) cout<<B[1][i]<<" "; cout<<endl;
// for (int i=0;i<=n;i++) cout<<B[2][i]<<" "; cout<<endl;
int rem=d[1]+d[2],tot=1; if (b[1][2]) rem--;
for (int w=0;w<=now;w++){
rem-=B[1][w]+B[2][w];
ans=(ans+((1ll*way*tot%mo)<<rem))%mo;
// cout<<"update "<<way<<" "<<tot<<" "<<rem1<<" "<<rem2<<endl;
if (B[1][w]==0||B[2][w]==0) break;
tot=1ll*tot*((1<<B[1][w]+B[2][w])-(1<<B[1][w])-(1<<B[2][w])+1)%mo;
}
return;
}
int rem=d[k]; int tot=1;
for (int w=0;w<=now;w++){
for (int i=1;i<k;i++) if (b[i][k]) B[i][w]++;
rem-=B[k][w];
get(k-1,max(w+1,now),((1ll*way*tot%mo)<<rem)%mo);
for (int i=1;i<k;i++) if (b[i][k]) B[i][w]--;
// cout<<k<<" "<<w<<" "<<B[k][w]<<endl;
if (B[k][w]==0) break;
tot=1ll*tot*(two[B[k][w]]-1)%mo;
}
}
int main(){
// freopen("data.in","r",stdin);
scanf("%d%d",&n,&m); int prem=m; two[0]=1;
for (int i=1;i<=m;i++) two[i]=two[i-1]*2%mo;
if (n==2){
printf("%d\n",m); return 0;
}
for (;m;m--){
int k1,k2; scanf("%d%d",&k1,&k2); b[k1][k2]=1; d[k1]++;
}
get(n,0,1); //cout<<ans<<" "<<two[prem]<<endl;
ans=(two[prem]-ans+mo)%mo;
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time
2017-06-18 22:32:04+0900
Task
F - Games on DAG
User
KujouKaren
Language
C++14 (GCC 5.4.1)
Score
1600
Code Size
1518 Byte
Status
AC
Exec Time
1978 ms
Memory
384 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:38:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m); int prem=m; two[0]=1;
^
./Main.cpp:44:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int k1,k2; scanf("%d%d",&k1,&k2); b[k1][k2]=1; d[k1]++;
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1600 / 1600
Status
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
4 ms
256 KB
0_03.txt
AC
1 ms
256 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
1975 ms
256 KB
1_04.txt
AC
1060 ms
256 KB
1_05.txt
AC
1978 ms
256 KB
1_06.txt
AC
268 ms
256 KB
1_07.txt
AC
464 ms
256 KB
1_08.txt
AC
1898 ms
256 KB
1_09.txt
AC
797 ms
256 KB
1_10.txt
AC
860 ms
256 KB
1_11.txt
AC
691 ms
256 KB
1_12.txt
AC
1411 ms
256 KB
1_13.txt
AC
1032 ms
256 KB
1_14.txt
AC
1621 ms
256 KB
1_15.txt
AC
466 ms
256 KB
1_16.txt
AC
401 ms
256 KB
1_17.txt
AC
1715 ms
256 KB
1_18.txt
AC
104 ms
384 KB
1_19.txt
AC
1639 ms
256 KB
1_20.txt
AC
1 ms
256 KB
1_21.txt
AC
1 ms
256 KB
1_22.txt
AC
5 ms
256 KB
1_23.txt
AC
29 ms
256 KB
1_24.txt
AC
1 ms
256 KB
1_25.txt
AC
1 ms
256 KB
1_26.txt
AC
154 ms
256 KB
1_27.txt
AC
1 ms
256 KB
1_28.txt
AC
1 ms
256 KB
1_29.txt
AC
22 ms
256 KB
1_30.txt
AC
1 ms
256 KB
1_31.txt
AC
527 ms
256 KB
1_32.txt
AC
26 ms
256 KB
1_33.txt
AC
1 ms
256 KB
1_34.txt
AC
3 ms
256 KB
1_35.txt
AC
10 ms
256 KB