結果

問題 No.1669 パズル作成
コンテスト
ユーザー hos.lyric
提出日時 2021-09-03 22:03:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 148 ms / 2,000 ms
コード長 2,736 bytes
コンパイル時間 1,711 ms
コンパイル使用メモリ 126,728 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2024-12-15 13:25:24
合計ジャッジ時間 5,065 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

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