Submission #43772333

---

Source Code Expand

// LUOGU_RID: 116589446
#include<cstdio>
using namespace std;
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
const int N=10,M=1<<N,K=N*(N-1)/2+1;
int f[N+1][M][M],n,t,m,mm,jc;
bool st[N][N],st2[M][M];
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    #endif
    // Insert Code Here
    scanf("%d%d%d",&n,&t,&m);
    E(i, m){
        int a,b;
        scanf("%d%d",&a,&b);
        st[a-1][b-1]=1;
    }
    jc=1;
    E(i, t)jc*=i;
    mm=(1<<n)-1;
    for(int i=0;i<=mm;++i)
        for(int j=0;j<n;++j){
            bool flag=1;
            for(int k=0;k<n;++k){
                int x=k<j?k:j,y=k>j?k:j;
                if(i>>k&1&&st[x][y]){
                    flag=0;
                    break;
                }
            }
            if(flag)
                st2[i][1<<j]=1;
        }
    // printf("st2[1][2]=%d\n",st2[1][2]);
    f[0][0][0]=1;
    for(int i=0;i<=t;++i)
        for(int j=0;j<=mm;++j)
            for(int k=0;k<=mm;++k){
                if(!f[i][j][k])continue;
                // if(i==1&&j==1&&k==1){
                //     puts("Start debug!");
                // }
                // printf("f[%d][%d][%d]=%d\n",i,j,k,f[i][j][k]);
                // for(int l=0;l<n;++l){
                //     if(j>>l&1)printf("have %d\n",l+1);
                // }
                // for(int l=0;l<n;++l){
                //     if(k>>l&1)printf("have chosen %d\n",l+1);
                // }
                int pos=k^mm;
                for(;pos;pos-=pos&-pos){
                    int low=pos&-pos;
                    if(i&&st2[j][low]&&low>j){
                        // if(i==1&&(j|low)==11&&(k|low)==11)
                        //     puts("Start debug!");
                        f[i][j|low][k|low]+=f[i][j][k];
                    }
                    if((i<t&&j)||!i){
                        // if(i+1==1&&low==11&&(k|low)==11)
                        //     puts("Start debug!");
                        f[i+1][low][k|low]+=f[i][j][k];
                    }
                }
            }
    int ans=0;
    for(int i=1;i<=mm;++i)ans+=f[t][i][mm];
    printf("%d",ans/jc);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:23:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   23 |     scanf("%d%d%d",&n,&t,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
./Main.cpp:26:14: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   26 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

Judge Result