Submission #1367806

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

class Solution {
public:
    unsigned long long popcnt(unsigned long long n) {
        unsigned long long c = 0;
        c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555);
        c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333);
        c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f);
        c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff);
        c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff);
        c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff);
        return(c);
    }

    unsigned long long tzcnt(unsigned long long n) {
        return(popcnt(~n & (n - 1)));
    }

    void solve(std::istream& in, std::ostream& out) {
        int N, E, x, y;
        int d[12][12];
        in >> N >> E;
        memset(d, 0, sizeof(d));

        rep(i, E) {
            in >> x >> y;
            d[x - 1][y - 1]++;
            d[y - 1][x - 1]++;
        }

        int len = 1;
        rep(i, N) {
            len <<= 1;
            d[i][i] = 1;
        }

        int ans = 1;
        reu(i, 1, len) {
            int cnt = 0;
            int j = i;
            int n = tzcnt(j);
            int b = n;
            int s = n;
            while (j) {
                b = n;
                n = tzcnt(j & -j);
                if (d[b][n]) cnt++;
                j -= j & -j;
            }
            if (d[n][s]) cnt++;
            if (popcnt(i) == cnt - 1) amax(ans, cnt - 1);
        }

        out << ans << endl;
    }
};

void solve(std::istream& in, std::ostream& out)
{
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}

#include <fstream>
#include <iostream>

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    istream& in = cin;
    ostream& out = cout;
    solve(in, out);
    return 0;
}

Submission Info

Judge Result