提出 #67156000

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

/*
*/

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    set<pair<int, int>> edges;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        if(u > v) swap(u, v);
        edges.insert({u, v});
    }
    vector<int> a(n);
    iota(a.begin(), a.end(), 1);
    int ans = 1e5;
    do {
        for(int k = 3; k <= n; k++) {
            // this length cycles
            set<pair<int, int>> req;
            int cur = 0;
            for(int i = 1; i < n; i++) {
                if(i % k) req.insert({min(a[i - 1], a[i]), max(a[i - 1], a[i])});
                if(i % k == k - 1) {
                    int j = i - k + 1;
                    req.insert({min(a[j], a[i]), max(a[j], a[i])});
                }
            }
            int rem = n % k;
            if(rem > 0 && rem < 3) {
                continue;
            }
            if(rem > 0) {
                int start = n - rem;
                req.insert({min(a[start], a[n - 1]), max(a[start], a[n - 1])});
            }
            for(auto [u, v]: req) {
                if(!edges.count({u, v})) cur++;
            }
            for(auto [u, v]: edges) {
                if(!req.count({u, v})) cur++;
            }
            ans = min(ans, cur);
        }
    } while(next_permutation(a.begin(), a.end()));
    cout << ans << '\n';
}

提出情報

ジャッジ結果