Submission #17426863


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];
    for(int i=0;i<(1<<N);i++){
        ok[i]=(1<<N)-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++){
        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++){
        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 0
Code Size 1912 Byte
Status
Exec Time 138 ms
Memory 15888 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
× 2
× 1
× 33
× 18
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 13 ms 11788 KB
sample_02.txt 10 ms 11536 KB
sample_03.txt 10 ms 11576 KB
subtask_1_1.txt 10 ms 11736 KB
subtask_1_10.txt 119 ms 15832 KB
subtask_1_11.txt 15 ms 11732 KB
subtask_1_12.txt 108 ms 15780 KB
subtask_1_13.txt 98 ms 13552 KB
subtask_1_14.txt 138 ms 15596 KB
subtask_1_15.txt 11 ms 11680 KB
subtask_1_16.txt 118 ms 15596 KB
subtask_1_17.txt 112 ms 15772 KB
subtask_1_18.txt 111 ms 15816 KB
subtask_1_19.txt 12 ms 11588 KB
subtask_1_2.txt 134 ms 15768 KB
subtask_1_20.txt 114 ms 15816 KB
subtask_1_21.txt 111 ms 15604 KB
subtask_1_22.txt 110 ms 15780 KB
subtask_1_23.txt 12 ms 11740 KB
subtask_1_24.txt 18 ms 11976 KB
subtask_1_25.txt 115 ms 15656 KB
subtask_1_26.txt 107 ms 15808 KB
subtask_1_27.txt 109 ms 15760 KB
subtask_1_28.txt 109 ms 15832 KB
subtask_1_29.txt 109 ms 15640 KB
subtask_1_3.txt 27 ms 12204 KB
subtask_1_30.txt 12 ms 11768 KB
subtask_1_31.txt 15 ms 11556 KB
subtask_1_32.txt 13 ms 11648 KB
subtask_1_33.txt 17 ms 11764 KB
subtask_1_34.txt 113 ms 15776 KB
subtask_1_35.txt 112 ms 15812 KB
subtask_1_36.txt 110 ms 15728 KB
subtask_1_37.txt 107 ms 15788 KB
subtask_1_38.txt 110 ms 15676 KB
subtask_1_39.txt 110 ms 15612 KB
subtask_1_4.txt 108 ms 15776 KB
subtask_1_40.txt 110 ms 15784 KB
subtask_1_41.txt 110 ms 15676 KB
subtask_1_42.txt 109 ms 15784 KB
subtask_1_43.txt 117 ms 15776 KB
subtask_1_44.txt 109 ms 15812 KB
subtask_1_45.txt 119 ms 15776 KB
subtask_1_46.txt 135 ms 15888 KB
subtask_1_47.txt 112 ms 15740 KB
subtask_1_48.txt 108 ms 15664 KB
subtask_1_5.txt 41 ms 12692 KB
subtask_1_6.txt 109 ms 15664 KB
subtask_1_7.txt 44 ms 12532 KB
subtask_1_8.txt 112 ms 15828 KB
subtask_1_9.txt 65 ms 13732 KB