提出 #70053909

---

ソースコード 拡げる

#include <bits/stdc++.h>

// =============================================================================
// 入力
// =============================================================================

// 可変長汎用入力関数
void in_impl () {}

template <typename T, typename... TS>
void in_impl (T& head, TS&... tail) {
    std::cin >> head;
    in_impl(tail ...);
}

// 可変長汎用入力マクロ
#define IN(T, ...) T __VA_ARGS__; in_impl(__VA_ARGS__)

// pair<T1,T2>の入力
template <typename T1, typename T2>
std::istream& operator>> (std::istream& is, std::pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

// vector<T>の入力
template <typename T>
std::istream& operator>> (std::istream& is, std::vector<T>& v) {
    for (auto&& vi : v) is >> vi;
    return is;
}


// =============================================================================
// 出力
// =============================================================================

// pair<T1,T2>の出力
template <typename T1, typename T2>
std::ostream& operator<< (std::ostream& os, const std::pair<T1, T2>& p) {
    os << p.first << ' ' << p.second;
    return os;
}

// vector<T>の出力
template <typename T>
std::ostream& operator<< (std::ostream& os, const std::vector<T>& v) {
    for (int i = 0, s = v.size(); i < s; ++i) {
        if (i) os << ' ';
        os << v[i];
    }
    return os;
}

// set<T>の出力
template <typename T>
std::ostream& operator<< (std::ostream& os, const std::set<T>& st) {
    auto itr = st.begin();
    int n = st.size();
    for (int i = 0; i < n; ++i, ++itr) {
        if (i) os << ' ';
        os << (*itr);
    }
    return os;
}

// multiset<T>の出力
template <typename T>
std::ostream& operator<< (std::ostream& os, const std::multiset<T>& st) {
    auto itr = st.begin();
    int n = st.size();
    for (int i = 0; i < n; ++i, ++itr) {
        if (i) os << ' ';
        os << (*itr);
    }
    return os;
}

// unordered_set<T>の出力
template <typename T>
std::ostream& operator<< (std::ostream& os, const std::unordered_set<T>& st) {
    auto itr = st.begin();
    int n = st.size();
    for (int i = 0; i < n; ++i, ++itr) {
        if (i) os << ' ';
        os << (*itr);
    }
    return os;
}

// map<Key,Val>の出力
template <typename Key, typename Val>
std::ostream& operator<< (std::ostream& os, const std::map<Key, Val>& mp) {
    auto itr = mp.begin();
    int n = mp.size();
    for (int i = 0; i < n; ++i, ++itr) {
        if (i) os << ' ';
        auto [key, val] = *itr;
        os << key << ':' << val;
    }
    return os;
}

// unordered_map<Key,Val>の出力
template <typename Key, typename Val>
std::ostream& operator<< (std::ostream& os, const std::unordered_map<Key, Val>& mp) {
    auto itr = mp.begin();
    int n = mp.size();
    for (int i = 0; i < n; ++i, ++itr) {
        if (i) os << ' ';
        auto [key, val] = *itr;
        os << key << ':' << val;
    }
    return os;
}


// =============================================================================
// ハッシュ（unordered_XXXで使用する）
// =============================================================================

// hashを組み合わせる関数
// 参考: boost::hash_combine（https://www.boost.org/doc/libs/1_55_0/doc/html/hash/reference.html#boost.hash_combine）
template <typename T>
size_t hash_combine (const size_t seed, const T& x) {
    return seed ^ (std::hash<T>()(x) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}

// pair用のhash
template <typename T1, typename T2>
struct std::hash<std::pair<T1, T2>> {
    size_t operator() (const std::pair<T1, T2>& p) const noexcept {
        size_t seed = 0;
        seed = hash_combine(seed, p.first);
        seed = hash_combine(seed, p.second);
        return seed;
    }
};

// tuple用のhash
template <int N>
struct HashTuple {
    template <typename Tuple>
    size_t operator() (const Tuple& tuple) const noexcept {
        size_t seed = HashTuple<N-1>()(tuple);
        return hash_combine(seed, std::get<N-1>(tuple));
    }
};
template <>
struct HashTuple<0> {
    template <typename Tuple>
    size_t operator() (const Tuple& tuple) const noexcept {
        return 0;
    }
};
template <typename... Args>
struct std::hash<std::tuple<Args...>> {
    size_t operator() (const std::tuple<Args...>& tuple) const noexcept {
        return HashTuple<std::tuple_size<std::tuple<Args...>>::value>()(tuple);
    }
};


// =============================================================================
// マクロ
// =============================================================================

// 反復
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define REP_2(i, N) for (int i = 0; i < (int)(N); ++i)
#define REP_3(i, A, B) for (int i = (A); i < (int)(B); ++i)
#define rep(...) GET_REP(__VA_ARGS__, REP_3, REP_2)(__VA_ARGS__)
#define RREP_2(i, N) for (int i = (int)(N)-1; i >= 0; --i)
#define RREP_3(i, A, B) for (int i = (int)(B)-1; i >= (int)(A); --i)
#define rrep(...) GET_REP(__VA_ARGS__, RREP_3, RREP_2)(__VA_ARGS__)

// イテレータ
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

// メンバ変数・関数
#define fst first
#define scd second
#define PB push_back
#define EB emplace_back

// 文字
#define el '\n'
#define spa ' '

// Yes, No
#define YES std::cout << "YES" << std::endl
#define NO std::cout << "NO" << std::endl
#define Yes std::cout << "Yes" << std::endl
#define No std::cout << "No" << std::endl
#define yes std::cout << "yes" << std::endl
#define no std::cout << "no" << std::endl
#define YESNO(b) std::cout << ((b) ? "YES" : "NO") << std::endl
#define YesNo(b) std::cout << ((b) ? "Yes" : "No") << std::endl
#define yesno(b) std::cout << ((b) ? "yes" : "no") << std::endl

// デバッグ
#define debug(x) std::cerr << #x << " = " << (x) << std::endl

// using宣言
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpii = vector<pii>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vpll = vector<pll>;

// 定数
constexpr int INF = std::numeric_limits<int>::max();
constexpr ll INFLL = std::numeric_limits<ll>::max();
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
const vpii DX = {{-1,0},{1,0},{0,-1},{0,1}};


int main () {
    IN(int, n, m);
    vpii E(m);
    rep(i, m) {
        IN(int, u, v);
        --u, --v;
        E[i] = {u, v};
    }
    int res = m;
    vi color(n);
    for (int i = 0, p = 1<<n; i < p; ++i) {
        for (int j = i, k = 0; k < n; ++k, j >>= 1) {
            if (j&1) {
                color[k] = 1;
            }
            else {
                color[k] = 0;
            }
        }
        int cnt = 0;
        rep(l, m) {
            auto [u, v] = E[l];
            if (color[u] != color[v]) ++cnt;
        }
        res = min(res, m-cnt);
    }
    cout << res << endl;
}

提出情報

ジャッジ結果