提出 #63635706

---

ソースコード 拡げる

#include <bits/stdc++.h>

#include <atcoder/dsu>

using namespace std;

vector<pair<int, int>> P_edge = {{0, 1}, {1, 2}, {2, 3}, {0, 3}, {3, 4}};
// Pを含むか判定する
// メモ化する
vector<int> memo_P(int(1 << 10), -1);
bool _is_P(vector<vector<bool>>& mat, vector<int> s) {  // 隣接行列 mat, 頂点集合 s
    int n = s.size();
    assert(n == 5);

    // メモ化するためにグラフにidxを振る
    int g_idx = 0;
    int pos = 0;
    for (int i = 0; i < 5; i++) {
        for (int j = i + 1; j < n; j++) {
            if (mat[s[i]][s[j]]) {
                g_idx |= 1 << pos;
            }
            pos++;
        }
    }

    if (memo_P[g_idx] != -1) return memo_P[g_idx];

    sort(s.begin(), s.end());
    do {  // P_edgeの辺がすべて存在すればOK
        bool ok = true;
        for (auto [u, v] : P_edge) {
            if (!mat[s[u]][s[v]]) ok = false;
        }
        if (ok) return memo_P[g_idx] = true;
    } while (next_permutation(s.begin(), s.end()));
    return memo_P[g_idx] = false;
}

vector<pair<int, int>> C_edge = {{0, 1}, {1, 2}, {2, 3}, {3, 4}};
// Pを含むか判定する
// メモ化する
vector<int> memo_C(int(1 << 10), -1);
bool _is_C(vector<vector<bool>>& mat, vector<int> s) {  // 隣接行列 mat, 頂点集合 s
    int n = s.size();
    assert(n == 5);

    // メモ化するためにグラフにidxを振る
    int g_idx = 0;
    int pos = 0;
    for (int i = 0; i < 5; i++) {
        for (int j = i + 1; j < n; j++) {
            if (mat[s[i]][s[j]]) {
                g_idx |= 1 << pos;
            }
            pos++;
        }
    }

    if (memo_C[g_idx] != -1) return memo_C[g_idx];

    sort(s.begin(), s.end());
    do {  // C_edgeの辺がすべて存在すればOK
        bool ok = true;
        for (auto [u, v] : C_edge) {
            if (!mat[s[u]][s[v]]) ok = false;
        }
        if (ok) return memo_C[g_idx] = true;
    } while (next_permutation(s.begin(), s.end()));
    return memo_C[g_idx] = false;
}

int longest_path(vector<vector<int>>& g) {
    int n = g.size();
    // bitDPでグラフの最長パスを求める
    vector<vector<int>> dp(1 << n, vector<int>(n, -100));
    for (int i = 0; i < n; i++) dp[1 << i][i] = 1;
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++)
            if (dp[i][j] != -100) {
                for (int nj : g[j]) {
                    if (i & (1 << nj)) continue;
                    dp[i | (1 << nj)][nj] = max(dp[i | (1 << nj)][nj], dp[i][j] + 1);
                }
            }
    }
    int mx = 0;
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) mx = max(mx, dp[i][j]);
    }
    return mx;
}

// P を判定する
bool is_P(vector<vector<int>>& g) {
    int n = g.size();
    if (n < 5) return false;

    // 隣接行列を作る
    vector<vector<bool>> mat(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < g[i].size(); j++) {
            mat[i][g[i][j]] = true;
        }
    }

    vector<int> perm(n, 0);
    for (int i = 0; i < 5; i++) perm[n - i - 1] = 1;
    do {  // すべての分け方について調べる
        vector<int> s;
        for (int i = 0; i < n; i++) {
            if (perm[i] == 1) s.push_back(i);
        }
        if (_is_P(mat, s)) return true;

    } while (next_permutation(perm.begin(), perm.end()));
    return false;
}

// P+P, P+C, C+C を判定する
// 0から順番に P+P, P+C, C+C, null
int is_P_pulus_P(vector<vector<int>>& g) {  // P+P, P+C, C+C
    int n = g.size();
    assert(n == 10);

    // 隣接行列を作る
    vector<vector<bool>> mat(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < g[i].size(); j++) {
            mat[i][g[i][j]] = true;
        }
    }

    bool is_P_C = false;
    bool is_C_C = false;

    vector<int> perm(n, 0);
    for (int i = 5; i < n; i++) perm[i] = 1;
    do {  // すべての分け方について調べる
        vector<int> s1, s2;
        for (int i = 0; i < n; i++) {
            if (perm[i] == 0)
                s1.push_back(i);
            else
                s2.push_back(i);
        }
        bool is_P1 = _is_P(mat, s1);
        bool is_C1 = _is_C(mat, s1);
        bool is_P2 = _is_P(mat, s2);
        bool is_C2 = _is_C(mat, s2);
        if (is_P1 && is_P2) return 0;
        if ((is_P1 && is_C2) || (is_C1 && is_P2)) is_P_C = true;
        if (is_C1 && is_C2) is_C_C = true;

    } while (next_permutation(perm.begin(), perm.end()));
    if (is_P_C) return 1;
    if (is_C_C) return 2;
    return 3;
}

// 連結成分を分類する
// 0から順番に P+P, P+C, C+C/N/P, C+C/N, C+C, P/N, P/U, N, U, P, C, null
int classification(vector<vector<int>>& g) {
    int n = g.size();
    if (n == 10) {
        int res = is_P_pulus_P(g);
        if (res == 0) return 0;  // P+P
        if (res == 1) return 1;  // P+C
        if (res == 2) {
            if (is_P(g)) return 2;  // C+C/N/P
            int dist = longest_path(g);
            if (dist >= 7)
                return 3;  // C+C/N
            else
                return 4;  // C+C
        }
    }
    if (is_P(g)) {
        int dist = longest_path(g);
        if (dist >= 7)
            return 5;  // P/N
        else if (dist >= 6)
            return 6;  // P/U
        else
            return 9;  // P
    } else {
        int dist = longest_path(g);
        if (dist >= 7)
            return 7;  // N
        else if (dist >= 6)
            return 8;  // U
        else if (dist >= 5)
            return 10;  // C
        else
            return 11;  // null
    }
}

int main() {
    // 入力
    int n, m;
    cin >> n >> m;
    atcoder::dsu uf(n);
    vector<pair<int, int>> edge(m);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        edge[i] = {u, v};
        uf.merge(u, v);
    }

    vector<pair<int, int>> idx(n);  // 頂点がどのグループの何番目の要素か
    vector<vector<int>> group = uf.groups();
    for (int i = 0; i < group.size(); i++) {
        assert(group[i].size() <= 10);  // 連結成分数は10以下
        for (int j = 0; j < group[i].size(); j++) {
            idx[group[i][j]] = {i, j};
        }
    }

    vector<vector<vector<int>>> g(group.size());  // 各連結成分についてグラフをつくる
    for (int i = 0; i < group.size(); i++) {
        g[i].assign(group[i].size(), vector<int>());
    }
    for (auto [u, v] : edge) {
        assert(idx[u].first == idx[v].first);
        int i = idx[u].second;
        int j = idx[v].second;
        g[idx[u].first][i].push_back(j);
        g[idx[u].first][j].push_back(i);
    }

    // P+P, P+C, C+C/N/P, C+C/N, C+C, P/N, P/U, N, U, P, C, null
    vector<int> cnt(12, 0);

    for (int i = 0; i < group.size(); i++) {
        cnt[classification(g[i])]++;
    }

    // 二分探索
    int ok = 0, ng = n;
    while (ng - ok > 1) {
        int mid = (ok + ng) / 2;
        bool fn = false;
        // P+P, P+C を分解する数を全探索
        for (int i = 0; i <= cnt[0] + cnt[1]; i++) {
            // P+P, P+C, C+C/N/P, C+C/N, C+C, P/N, P/U, N, U, P, C, null
            vector<int> cur = cnt;

            // 分解する順番は P+P -> P+C でよい
            int cut_0 = min(cnt[0], i);
            int cut_1 = i - cut_0;

            cur[0] -= cut_0;
            cur[9] += cut_0 * 2;

            cur[1] -= cut_1;
            cur[9] += cut_1;
            cur[10] += cut_1;

            // Pを詰め込む
            int P = mid;

            vector<int> P_order = {9, 6, 5, 2};

            int dec = 0;

            for (int i : P_order) {
                dec = min(cur[i], P);
                P -= dec;
                cur[i] -= dec;
                if (i == 1) cur[10] += dec;  // Cを増やす
            }

            // Nを詰め込む
            int N = mid;

            vector<int> N_order = {7, 5, 3, 2, 1, 0};

            for (int i : N_order) {
                dec = min(cur[i], N);
                N -= dec;
                cur[i] -= dec;
            }

            // Uを詰め込む
            int U = mid;

            vector<int> U_order = {8, 6, 7, 5, 4, 3, 2, 1, 0};

            for (int i : U_order) {
                dec = min(cur[i], U);
                U -= dec;
                cur[i] -= dec;
            }

            // Cを詰め込む
            int C = mid;

            vector<int> C_order = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

            for (int i : C_order) {
                if (i <= 4) {
                    dec = min(cur[i] * 2, C);
                } else {
                    dec = min(cur[i], C);
                }
                C -= dec;
            }

            if (N == 0 && U == 0 && P == 0 && C == 0) {
                fn = true;
                break;
            }
        }
        if (fn)
            ok = mid;
        else
            ng = mid;
    }
    cout << ok << endl;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘bool _is_P(std::vector<std::vector<bool> >&, std::vector<int>)’:
Main.cpp:35:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   35 |         if (ok) return memo_P[g_idx] = true;
Main.cpp:37:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   37 |     return memo_P[g_idx] = false;
Main.cpp: In function ‘bool _is_C(std::vector<std::vector<bool> >&, std::vector<int>)’:
Main.cpp:68:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   68 |         if (ok) return memo_C[g_idx] = true;
Main.cpp:70:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   70 |     return memo_C[g_idx] = false;
Main.cpp: In function ‘bool is_P(std::vector<std::vector<int> >&)’:
Main.cpp:102:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  102 |         for (int j = 0; j < g[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
Main.cpp: In function ‘int is_P_pulus_P(std::vector<std::vector<int> >&)’:
Main.cpp:129:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  129 |         for (int j = 0; j < g[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:215:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  215 |     for (int i = 0; i < group.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
Main.cpp:217:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  217 |         for (int j = 0; j < group[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~
Main.cpp:223:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  223 |     for (int i = 0; i < group.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
Main.cpp:237:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  237 |     for (int i = 0; i < group.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

ジャッジ結果