結果
問題 | No.1669 パズル作成 |
ユーザー |
![]() |
提出日時 | 2021-09-19 21:33:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 843 ms / 2,000 ms |
コード長 | 2,271 bytes |
コンパイル時間 | 5,467 ms |
コンパイル使用メモリ | 207,492 KB |
最終ジャッジ日時 | 2025-01-24 15:55:55 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct UnionFind { vector<int> par; vector<int> size; UnionFind(int n) { par.resize(n); size.resize(n,1); for(int i = 0; i < n; i++) { par[i] = i; } } int find(int x) { if(par[x] == x) { return x; } return par[x] = find(par[x]); } bool same(int x, int y) { return find(x) == find(y); } int consize(int x) { return size[find(x)]; } void unite(int x, int y) { x = find(x); y = find(y); if(x == y) { return; } if(size[x] < size[y]) { par[x] = y; size[y] += size[x]; } else { par[y] = x; size[x] += size[y]; } } }; int inf = 1001001001; int main() { int N,M; cin >> N >> M; if(M == 0) { cout << 0 << endl; return 0; } UnionFind uf(2*N); for(int i = 0; i < M; i++) { int r,c; cin >> r >> c; r--; c--; uf.unite(r,N+c); } map<int,pair<int,int>>tmp; for(int i = 0; i < 2*N; i++) { if(i < N) { tmp[uf.find(i)].first++; } else { tmp[uf.find(i)].second++; } } int n = tmp.size(); vector<vector<int>>dp1(n+1,vector<int>(N+1,-inf)),dp2(n+1,vector<int>(N+1,inf)); dp1[0][0] = 0; dp2[0][0] = 0; int k = 0; for(auto x:tmp) { for(int j = 0; j <= N; j++) { dp1[k+1][j] = max(dp1[k+1][j],dp1[k][j]); dp2[k+1][j] = min(dp2[k+1][j],dp2[k][j]); if(j+x.second.first <= N) { dp1[k+1][j+x.second.first] = max(dp1[k+1][j+x.second.first],dp1[k][j]+x.second.second); dp2[k+1][j+x.second.first] = min(dp2[k+1][j+x.second.first],dp2[k][j]+x.second.second); } } k++; } int ans = inf; for(int i = 0; i <= N; i++) { if(dp1[n][i] >= 0) { int a = i,b = dp1[n][i]; ans = min(ans,a*b+(N-a)*(N-b)-M); } if(dp2[n][i] != inf) { int a = i,b = dp2[n][i]; ans = min(ans,a*b+(N-a)*(N-b)-M); } } cout << ans << endl; }