Submission #19458399


Source Code Expand

Copy
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rrep(i,n) for(ll i=n-1; i>=0; i--)
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef pair<ll,Pll> PlP;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
string zero_padding(int val, int nf){ ostringstream sout;sout << setfill('0') << setw(nf) << val; return sout.str();};
ull mo = 1000000007;
ld PI=asin(1)*2;
//using namespace atcoder;

bool D[41][41];
int main(){
    ll N,M;
    cin >> N >> M;
    vector<ll> a(M), b(M);
    vector<vector<ll>> G(N);
    rep(i,M){
        cin >> a[i] >> b[i];
        a[i]--;b[i]--;
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
        D[a[i]][b[i]] = 1;
        D[b[i]][a[i]] = 1;
    }
    ll K = N / 2;
    ll L = N - K;
    vector<bool> ok((1LL << K), 1);
    rep(i,M){
        if((a[i] < K) && (b[i] < K)){
            ok[(1LL << a[i]) | (1LL << b[i])] = 0;
        }
    }
    rep(bit,(1LL << K)){
        if(ok[bit]) continue;
        rep(i,K){
            ok[bit | (1LL << i)] = 0;
        }
    }
    vector<ll> dp((1LL << K), 0);
    dp[0] = ((1LL << L) - 1);
    rep(i,N){
        REP(j,i+1,N){
            if(i >= K) continue;
            if(j < K) continue;
            if(!D[i][j]){
                dp[1LL << i] |= (1LL << (j-K));                  
            }
        }
    }
    // PR(dp, dp.size());
    rep(bit,(1LL << K)){
        rep(i,K){
            if(!((bit >> i)&1LL)){
                dp[bit | (1LL << i)] = (dp[bit]&dp[(1LL << i)]);
            }
        }
    }
    // PR(dp, dp.size());
    vector<bool> pk((1LL << L), 1);
    rep(i,M){
        if((a[i] >= K) && (b[i] >= K)){
            ll aa = a[i] - K;
            ll bb = b[i] - K;
            pk[(1LL << aa) | (1LL << bb)] = 0;
        }
    }
    rep(bit,(1LL << L)){
        if(pk[bit]) continue;
        rep(i,L){
            pk[bit | (1LL << i)] = 0;
        }
    }
    vector<ll> ep((1LL << L), 0);
    rep(bit,(1LL << L)){
        if(!pk[bit]) continue;
        ep[bit] = __builtin_popcount(bit); 
    }
    rep(bit,(1LL << L)){
        rep(i,L){
            if(!((bit >> i)&1LL)){
                cmax(ep[bit | (1LL << i)], ep[bit]);
            }
        }
    }
    // PR(ok,ok.size());
    // PR(dp,dp.size());
    // PR(ep,ep.size());
    ll ans = 0;
    rep(bit,(1LL << K)){
        if(!ok[bit]) continue;
        ll t = __builtin_popcount(bit);
        t += ep[(dp[bit])];
        // if(t == 13){
        //     cout << bitset<20>(bit) << endl;
        // }
        cmax(ans, t); 
    }
    cout << ans << endl;
    // rep(bit, (1LL << L)){
    //     ll t = 0;
    //     rep(i,M){
    //         if(((bit >> a[i])&1LL) && ((bit >> b[i])&1LL)) goto gt2;
    //     }
    //     t = __builtin_popcount(bit);
    //     u.push_back({bit, t});
    //     gt2:
    //     continue;
    // }
}

Submission Info

Submission Time
Task G - Mixture Drug
User zssa
Language C++ (GCC 9.2.1)
Score 600
Code Size 3417 Byte
Status AC
Exec Time 196 ms
Memory 19904 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 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 AC 7 ms 3460 KB
sample_02.txt AC 3 ms 3600 KB
sample_03.txt AC 4 ms 3444 KB
subtask_1_1.txt AC 2 ms 3580 KB
subtask_1_10.txt AC 192 ms 19748 KB
subtask_1_11.txt AC 2 ms 3460 KB
subtask_1_12.txt AC 196 ms 19748 KB
subtask_1_13.txt AC 114 ms 15676 KB
subtask_1_14.txt AC 154 ms 19832 KB
subtask_1_15.txt AC 7 ms 3616 KB
subtask_1_16.txt AC 183 ms 19644 KB
subtask_1_17.txt AC 188 ms 19904 KB
subtask_1_18.txt AC 193 ms 19904 KB
subtask_1_19.txt AC 4 ms 3684 KB
subtask_1_2.txt AC 149 ms 19648 KB
subtask_1_20.txt AC 182 ms 19904 KB
subtask_1_21.txt AC 189 ms 19648 KB
subtask_1_22.txt AC 188 ms 19696 KB
subtask_1_23.txt AC 3 ms 3468 KB
subtask_1_24.txt AC 22 ms 4036 KB
subtask_1_25.txt AC 189 ms 19700 KB
subtask_1_26.txt AC 188 ms 19760 KB
subtask_1_27.txt AC 192 ms 19612 KB
subtask_1_28.txt AC 191 ms 19760 KB
subtask_1_29.txt AC 189 ms 19648 KB
subtask_1_3.txt AC 41 ms 6308 KB
subtask_1_30.txt AC 2 ms 3536 KB
subtask_1_31.txt AC 2 ms 3524 KB
subtask_1_32.txt AC 3 ms 3676 KB
subtask_1_33.txt AC 16 ms 3928 KB
subtask_1_34.txt AC 176 ms 19644 KB
subtask_1_35.txt AC 191 ms 19620 KB
subtask_1_36.txt AC 192 ms 19748 KB
subtask_1_37.txt AC 190 ms 19760 KB
subtask_1_38.txt AC 191 ms 19704 KB
subtask_1_39.txt AC 186 ms 19852 KB
subtask_1_4.txt AC 191 ms 19624 KB
subtask_1_40.txt AC 191 ms 19852 KB
subtask_1_41.txt AC 188 ms 19704 KB
subtask_1_42.txt AC 189 ms 19772 KB
subtask_1_43.txt AC 185 ms 19756 KB
subtask_1_44.txt AC 182 ms 19696 KB
subtask_1_45.txt AC 183 ms 19776 KB
subtask_1_46.txt AC 156 ms 19748 KB
subtask_1_47.txt AC 191 ms 19716 KB
subtask_1_48.txt AC 177 ms 19612 KB
subtask_1_5.txt AC 53 ms 7240 KB
subtask_1_6.txt AC 191 ms 19848 KB
subtask_1_7.txt AC 75 ms 9404 KB
subtask_1_8.txt AC 187 ms 19760 KB
subtask_1_9.txt AC 97 ms 11644 KB