結果
問題 | No.1479 Matrix Eraser |
ユーザー |
|
提出日時 | 2021-04-16 21:00:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 462 ms / 3,000 ms |
コード長 | 1,542 bytes |
コンパイル時間 | 5,800 ms |
コンパイル使用メモリ | 294,404 KB |
最終ジャッジ日時 | 2025-01-20 19:12:39 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
ソースコード
#pragma GCC optimize("Ofast")#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;typedef long long int ll;typedef unsigned long long ull;mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());ll myRand(ll B) {return (ull)rng() % B;}// N使ってる状態 0// M使ってる状態 1int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n,m; cin >> n >> m;vector<vector<int>> a(n,vector<int>(m));map<int,vector<pair<int,int>>> mp;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin >> a[i][j];mp[a[i][j]].push_back({i,j});}}int res=0;for(auto p:mp){if(p.first==0)continue;vector<int> v,vv;for(auto pp:p.second){v.push_back(pp.first);vv.push_back(pp.second);}sort(v.begin(), v.end());sort(vv.begin(), vv.end());v.erase(unique(v.begin(), v.end()),v.end());vv.erase(unique(vv.begin(), vv.end()),vv.end());int N=v.size(),M=vv.size();mf_graph<int> g(N+M+2);int S=N+M,T=N+M+1;for(int i=0;i<N;i++){g.add_edge(i,T,1);}for(int i=0;i<M;i++){g.add_edge(S,N+i,1);}for(auto pp:p.second){g.add_edge(N+(lower_bound(vv.begin(), vv.end(),pp.second)-vv.begin()),(lower_bound(v.begin(), v.end(),pp.first)-v.begin()),1e9);}res+=g.flow(S,T);}cout << res << endl;}