結果

問題 No.1669 パズル作成
ユーザー 👑 hos.lyrichos.lyric
提出日時 2021-09-03 22:03:31
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 159 ms / 2,000 ms
コード長 2,736 bytes
コンパイル時間 1,502 ms
コンパイル使用メモリ 120,976 KB
実行使用メモリ 7,120 KB
最終ジャッジ日時 2023-08-21 21:53:17
合計ジャッジ時間 5,240 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 3 ms
4,376 KB
testcase_04 AC 3 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 17 ms
4,380 KB
testcase_07 AC 54 ms
6,788 KB
testcase_08 AC 59 ms
7,072 KB
testcase_09 AC 74 ms
6,924 KB
testcase_10 AC 157 ms
6,912 KB
testcase_11 AC 122 ms
6,868 KB
testcase_12 AC 58 ms
7,012 KB
testcase_13 AC 58 ms
7,120 KB
testcase_14 AC 59 ms
7,024 KB
testcase_15 AC 143 ms
6,896 KB
testcase_16 AC 71 ms
6,808 KB
testcase_17 AC 73 ms
7,080 KB
testcase_18 AC 71 ms
6,892 KB
testcase_19 AC 74 ms
6,892 KB
testcase_20 AC 91 ms
6,796 KB
testcase_21 AC 118 ms
6,828 KB
testcase_22 AC 145 ms
6,892 KB
testcase_23 AC 159 ms
6,952 KB
testcase_24 AC 120 ms
6,864 KB
testcase_25 AC 104 ms
6,856 KB
testcase_26 AC 73 ms
6,804 KB
testcase_27 AC 83 ms
6,900 KB
testcase_28 AC 104 ms
6,904 KB
testcase_29 AC 81 ms
6,984 KB
testcase_30 AC 50 ms
6,860 KB
testcase_31 AC 51 ms
6,752 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int uf[10010];
int root(int u) {
  return (uf[u] < 0) ? u : (uf[u] = root(uf[u]));
}
bool connect(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}


int N, M;
vector<int> X, Y;

bitset<5010> dp[5010];

int main() {
  for (; ~scanf("%d%d", &N, &M); ) {
    X.resize(M);
    Y.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d", &X[i], &Y[i]);
      --X[i];
      --Y[i];
    }
    
    fill(uf, uf + N + N, -1);
    for (int i = 0; i < M; ++i) {
      connect(X[i], N + Y[i]);
    }
    vector<int> as(N + N, 0), bs(N + N, 0);
    for (int x = 0; x < N; ++x) {
      ++as[root(x)];
    }
    for (int y = 0; y < N; ++y) {
      ++bs[root(N + y)];
    }
    
    vector<pair<int, int>> ps;
    for (int r = 0; r < N + N; ++r) {
      if (uf[r] < 0) {
        ps.emplace_back(as[r], bs[r]);
      }
    }
    sort(ps.begin(), ps.end());
    const int psLen = ps.size();
// cerr<<"ps = ";pv(ps.begin(),ps.end());
    
    for (int a = 0; a <= N; ++a) {
      dp[a].reset();
    }
    dp[0][N] = true;
    for (int j = 0, k; j < psLen; j = k) {
      for (k = j; k < psLen && ps[j] == ps[k]; ++k) {}
      int num = k - j;
      for (int e = 0; num > 0; ++e) {
        const int t = min(1 << e, num);
        num -= t;
        const int da = t * ps[j].first;
        const int db = t * ps[j].second;
        for (int a = N - da; a >= 0; --a) {
          dp[a + da] |= dp[a] >> db;
        }
      }
    }
    
    int ans = N * N;
    for (int a = 0; a <= N; ++a) for (int b = 0; b <= N; ++b) {
      if (dp[a][b]) {
        chmin(ans, a * (N - b) + (N - a) * b);
      }
    }
    ans -= M;
    printf("%d\n", ans);
  }
  return 0;
}
0