結果
問題 | No.3060 Erase Binary Matrix |
ユーザー |
![]() |
提出日時 | 2025-03-14 23:11:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 3,773 bytes |
コンパイル時間 | 5,755 ms |
コンパイル使用メモリ | 264,320 KB |
実行使用メモリ | 7,328 KB |
最終ジャッジ日時 | 2025-03-14 23:12:10 |
合計ジャッジ時間 | 8,239 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 49 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000000 #define Inf64 1000000000000000001LL template <class S> struct potentialized_dsu { public: potentialized_dsu() : _n(0) {} potentialized_dsu(int n) : _n(n), parent_or_size(n, -1), d(n) {} int merge(int a, int b, S v) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]){ std::swap(x, y); std::swap(a, b); S t; v = t - v; } v += diff(x,a); v -= diff(y,b); d[y] += d[x] + v; parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; int l = leader(parent_or_size[a]); if(parent_or_size[a] != l){ d[a] += d[parent_or_size[a]]; parent_or_size[a] = l; } return parent_or_size[a]; } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } S diff(int a,int b){ assert(0 <= a && a < _n); assert(0 <= b && b < _n); leader(a); leader(b); return d[b] - d[a]; } std::vector<std::vector<int>> groups() { std::vector<int> leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector<std::vector<int>> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }), result.end()); return result; } private: int _n; // root node: -1 * component size // otherwise: parent std::vector<int> parent_or_size; std::vector<S> d; }; struct xorint{ using mytype = xorint; int v = 0; mytype operator+(mytype another)const{ return (mytype(*this)+=another); } mytype &operator+=(const mytype &another){ (*this).v ^= another.v; return (*this); } mytype operator-(mytype another)const{ return (mytype(*this)-=another); } mytype &operator-=(const mytype &another){ (*this).v ^= another.v; return (*this); } }; int main(){ int h,w; cin>>h>>w; vector<string> s(h); rep(i,h)cin>>s[i]; sort(s.begin(),s.end(),[&](string a,string b){ int x = 0,y = 0; rep(i,w){ if(a[i]=='1')x++; if(b[i]=='1')y++; } if(x!=y)return x<y; return a<b; }); scc_graph S(h); vector<int> u,v; rep(i,h){ for(int j=i+1;j<h;j++){ if(s[i]==s[j]){ S.add_edge(i,j); S.add_edge(j,i); } else{ bool f = true; rep(k,w){ if(s[i][k]=='1' && s[j][k]=='0')f = false; } if(f){ S.add_edge(i,j); u.push_back(i); v.push_back(j); } } } } auto ss = S.scc(); vector<int> pos(h); rep(i,ss.size()){ for(auto j:ss[i]){ pos[j] = i; } } vector<vector<int>> E(ss.size()); rep(i,u.size()){ E[pos[u[i]]].push_back(pos[v[i]]); } vector<int> dp(ss.size(),0); rep(i,ss.size()){ dp[i] += ss[i].size(); rep(j,E[i].size()){ dp[E[i][j]] = max(dp[E[i][j]],dp[i]); } } int ans = 0; rep(i,ss.size()){ ans = max(ans,dp[i]); } cout<<h-ans<<endl; return 0; }