Submission #17427036


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a,b,dp[1<<20],dp2[1<<20],N,A,M,ch[20],ok[1<<20],cnt,ans=1;
vector<int> v[40];
int main(){
    cin>>n>>m;
    N=n/2;
    M=n-n/2;
    for(int i=0;i<(1<<20);i++)dp[i]=dp2[i]=1;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        a--,b--;
        v[a].push_back(b);
        v[b].push_back(a);
        if(a<n/2&&b<n/2){
            A=(1<<a)|(1<<b);
            dp[A]=0;
        }
        else if(a>=n/2&&b>=n/2){
            a-=N;
            b-=N;
            A=(1<<a)|(1<<b);
            dp2[A]=0;
        }
        else{
            b-=N;
            ch[a]|=(1<<b);
        }
    }
    for(int i=0;i<(1<<N);i++){
        if(dp[i]==0){
            for(int j=0;j<N;j++){
                dp[i|(1<<j)]=0;
            }
        }
    }
    for(int i=0;i<(1<<M);i++){
        if(dp2[i]==0){
            for(int j=0;j<M;j++){
                dp2[i|(1<<j)]=0;
            }
        }
    }
    for(int i=0;i<N;i++)ch[i]=ch[i]^((1<<M)-1);
    for(int i=0;i<(1<<N);i++){
        ok[i]=(1<<M)-1;
        for(int j=0;j<N;j++){
            if((i>>j)&1)ok[i]&=ch[j];
        }
    }

    for(int i=0;i<(1<<N);i++){
        if(dp[i]==0)continue;
        cnt=0;
        for(int j=0;j<N;j++){
            if((i>>j)&1)cnt++;
        }
        dp[i]=cnt;
    }



    for(int i=0;i<(1<<M);i++){
        if(dp2[i]==0)continue;
        cnt=0;
        for(int j=0;j<M;j++){
            if((i>>j)&1)cnt++;
        }
        dp2[i]=cnt;
    }
    for(int i=0;i<(1<<M);i++){
        //cout<<dp2[i]<<" "<<i<<endl;
    }
    for(int i=0;i<(1<<M);i++){
        //if(dp2[i]==0)continue;
        for(int j=0;j<M;j++){
            //if(dp2[i|(1<<j)]>0){
                dp2[i|(1<<j)]=max(dp2[i|(1<<j)],dp2[i]);
            //}
        }
    }
    for(int i=0;i<(1<<N);i++){
        //cout<<dp[i]<<" "<<i<<" "<<ok[i]<<" "<<dp2[ok[i]]<<endl;
        if(dp[i]){
            ans=max(ans,dp[i]+dp2[ok[i]]);
        }
    }
    cout<<ans<<endl;
}

Submission Info

Submission Time
Task G - Mixture Drug
User alorie
Language C++ (GCC 9.2.1)
Score 600
Code Size 2073 Byte
Status
Exec Time 132 ms
Memory 15908 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
× 3
× 51
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt 14 ms 11624 KB
sample_02.txt 13 ms 11756 KB
sample_03.txt 12 ms 11812 KB
subtask_1_1.txt 12 ms 11728 KB
subtask_1_10.txt 127 ms 15672 KB
subtask_1_11.txt 13 ms 11744 KB
subtask_1_12.txt 128 ms 15716 KB
subtask_1_13.txt 94 ms 13792 KB
subtask_1_14.txt 131 ms 15868 KB
subtask_1_15.txt 14 ms 11760 KB
subtask_1_16.txt 132 ms 15724 KB
subtask_1_17.txt 127 ms 15828 KB
subtask_1_18.txt 128 ms 15796 KB
subtask_1_19.txt 12 ms 11652 KB
subtask_1_2.txt 129 ms 15792 KB
subtask_1_20.txt 128 ms 15800 KB
subtask_1_21.txt 131 ms 15828 KB
subtask_1_22.txt 128 ms 15736 KB
subtask_1_23.txt 13 ms 11704 KB
subtask_1_24.txt 22 ms 11880 KB
subtask_1_25.txt 124 ms 15896 KB
subtask_1_26.txt 125 ms 15672 KB
subtask_1_27.txt 125 ms 15712 KB
subtask_1_28.txt 124 ms 15828 KB
subtask_1_29.txt 125 ms 15904 KB
subtask_1_3.txt 28 ms 12256 KB
subtask_1_30.txt 9 ms 11628 KB
subtask_1_31.txt 16 ms 11592 KB
subtask_1_32.txt 10 ms 11820 KB
subtask_1_33.txt 21 ms 11940 KB
subtask_1_34.txt 127 ms 15852 KB
subtask_1_35.txt 126 ms 15684 KB
subtask_1_36.txt 124 ms 15712 KB
subtask_1_37.txt 126 ms 15740 KB
subtask_1_38.txt 124 ms 15688 KB
subtask_1_39.txt 127 ms 15700 KB
subtask_1_4.txt 125 ms 15744 KB
subtask_1_40.txt 126 ms 15908 KB
subtask_1_41.txt 126 ms 15696 KB
subtask_1_42.txt 127 ms 15876 KB
subtask_1_43.txt 128 ms 15716 KB
subtask_1_44.txt 124 ms 15864 KB
subtask_1_45.txt 127 ms 15820 KB
subtask_1_46.txt 127 ms 15828 KB
subtask_1_47.txt 127 ms 15808 KB
subtask_1_48.txt 131 ms 15864 KB
subtask_1_5.txt 39 ms 12824 KB
subtask_1_6.txt 126 ms 15792 KB
subtask_1_7.txt 52 ms 12760 KB
subtask_1_8.txt 125 ms 15796 KB
subtask_1_9.txt 71 ms 13672 KB