結果
問題 | No.1479 Matrix Eraser |
ユーザー | ningenMe |
提出日時 | 2021-04-16 22:49:00 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 278 ms / 3,000 ms |
コード長 | 6,807 bytes |
コンパイル時間 | 2,836 ms |
コンパイル使用メモリ | 238,596 KB |
実行使用メモリ | 24,440 KB |
最終ジャッジ日時 | 2024-07-03 03:07:21 |
合計ジャッジ時間 | 9,227 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 7 ms
14,900 KB |
testcase_01 | AC | 7 ms
14,764 KB |
testcase_02 | AC | 6 ms
14,980 KB |
testcase_03 | AC | 7 ms
14,996 KB |
testcase_04 | AC | 6 ms
14,956 KB |
testcase_05 | AC | 7 ms
15,004 KB |
testcase_06 | AC | 7 ms
14,980 KB |
testcase_07 | AC | 34 ms
15,896 KB |
testcase_08 | AC | 54 ms
16,476 KB |
testcase_09 | AC | 108 ms
17,976 KB |
testcase_10 | AC | 195 ms
20,260 KB |
testcase_11 | AC | 127 ms
18,564 KB |
testcase_12 | AC | 40 ms
15,984 KB |
testcase_13 | AC | 56 ms
16,516 KB |
testcase_14 | AC | 46 ms
16,084 KB |
testcase_15 | AC | 15 ms
15,184 KB |
testcase_16 | AC | 49 ms
16,308 KB |
testcase_17 | AC | 239 ms
21,040 KB |
testcase_18 | AC | 236 ms
21,252 KB |
testcase_19 | AC | 235 ms
21,188 KB |
testcase_20 | AC | 245 ms
21,208 KB |
testcase_21 | AC | 278 ms
21,176 KB |
testcase_22 | AC | 250 ms
21,160 KB |
testcase_23 | AC | 260 ms
21,192 KB |
testcase_24 | AC | 267 ms
21,164 KB |
testcase_25 | AC | 231 ms
21,200 KB |
testcase_26 | AC | 236 ms
21,176 KB |
testcase_27 | AC | 153 ms
17,840 KB |
testcase_28 | AC | 150 ms
18,124 KB |
testcase_29 | AC | 151 ms
18,076 KB |
testcase_30 | AC | 147 ms
18,076 KB |
testcase_31 | AC | 151 ms
18,144 KB |
testcase_32 | AC | 74 ms
24,440 KB |
testcase_33 | AC | 69 ms
24,332 KB |
testcase_34 | AC | 70 ms
24,316 KB |
testcase_35 | AC | 78 ms
24,244 KB |
testcase_36 | AC | 68 ms
24,340 KB |
testcase_37 | AC | 22 ms
17,196 KB |
testcase_38 | AC | 164 ms
17,180 KB |
testcase_39 | AC | 231 ms
22,792 KB |
testcase_40 | AC | 8 ms
14,960 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using int128 = __int128_t; using int64 = long long; using int32 = int; using uint128 = __uint128_t; using uint64 = unsigned long long; using uint32 = unsigned int; #define ALL(obj) (obj).begin(),(obj).end() template<class T> using priority_queue_reverse = priority_queue<T,vector<T>,greater<T>>; constexpr int64 MOD = 1'000'000'000LL + 7; //' constexpr int64 MOD2 = 998244353; constexpr int64 HIGHINF = 1'000'000'000'000'000'000LL; constexpr int64 LOWINF = 1'000'000'000'000'000LL; //' constexpr long double PI = 3.1415926535897932384626433L; template <class T> vector<T> multivector(size_t N,T init){return vector<T>(N,init);} template <class... T> auto multivector(size_t N,T... t){return vector<decltype(multivector(t...))>(N,multivector(t...));} template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}} template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;} template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;} template <class T>ostream &operator<<(ostream &o, const deque<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;} template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;} void print(void) {cout << endl;} template <class Head> void print(Head&& head) {cout << head;print();} template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);} template <class T> void chmax(T& a, const T b){a=max(a,b);} template <class T> void chmin(T& a, const T b){a=min(a,b);} vector<string> split(const string &str, const char delemiter) {vector<string> res;stringstream ss(str);string buffer; while( getline(ss, buffer, delemiter) ) res.push_back(buffer); return res;} inline constexpr int msb(int x) {return x?31-__builtin_clz(x):-1;} inline constexpr int64 ceil_div(const int64 a,const int64 b) {return (a+(b-1))/b;}// return ceil(a/b) void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;} void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;} void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;} /* * @title Zarts - 座標圧縮 * @docs md/util/Zarts.md */ template<class T> class Zarts{ vector<T> value; map<T,int> key; size_t sz; public: vector<int> compressed; Zarts(const vector<T> & ar, int light_flag = 0, T pre=-1) : compressed(ar.size()) { if(!light_flag) { for (auto &e : ar) key[e]; int cnt=0; for (auto &e : key) e.second = cnt++; for (int i=0;i<ar.size();++i) compressed[i]=key[ar[i]]; value.resize(key.size()); for (auto &e : key) value[e.second] = e.first; sz = cnt; } else { vector<pair<int,int>> ord(ar.size()); for(int i=0;i<ar.size();++i) ord[i]={ar[i],i}; sort(ord.begin(),ord.end()); int cnt=-1; for(int i=0;i<ar.size();++i) { if(pre < ord[i].first) cnt++; compressed[ord[i].second] = cnt; pre = ord[i].first; } sz = cnt+1; } } T get_value(int key) { return value[key]; } int get_key(T value) { assert(key.count(value)); return key[value]; } size_t size() { return sz; } }; /* * @title Dinic - Dinicフロー * @docs md/graph/Dinic.md */ template <class T> class Dinic { struct info { int to, rev; T cap; }; T ini, inf; vector<vector<info>> edge; vector<int> level, iter; inline void bfs(int start) { for (int i = 0; i < level.size(); ++i) level[i] = -1; queue<int> q; level[start] = 0; q.push(start); while (q.size()) { int from = q.front(); q.pop(); for (auto& e : edge[from]) { if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[from] + 1; q.push(e.to); } } } } inline T dfs(int from, int goal, T flow) { if (from == goal) return flow; for (int& i = iter[from]; i < edge[from].size(); ++i) { auto& e = edge[from][i]; if (e.cap <= 0 || level[from] >= level[e.to]) continue; T dflow = dfs(e.to, goal, min(flow, e.cap)); if (dflow <= 0) continue; e.cap -= dflow; edge[e.to][e.rev].cap += dflow; return dflow; } return ini; } public: Dinic(int N, T ini, T inf) : edge(N), level(N), iter(N), ini(ini), inf(inf) { // do nothing } inline void make_edge(int from, int to, T cap) { edge[from].push_back({ to, (int)edge[to].size(), cap }); edge[to].push_back({ from, (int)edge[from].size() - 1, ini }); } inline T maxflow(int start, int goal) { T maxflow = ini; while (1) { bfs(start); if (level[goal] < 0) return maxflow; for (int i = 0; i < iter.size(); ++i) iter[i] = 0; T flow; while ((flow = dfs(start, goal, inf))>0) maxflow += flow; } } }; //verify https://atcoder.jp/contests/arc085/tasks/arc085_c int solve(vector<pair<int,int>> vp) { int n = vp.size(); vector<int> Y(n),X(n); for(int i=0;i<n;++i) Y[i] = vp[i].first; for(int i=0;i<n;++i) X[i] = vp[i].second; Zarts<int> ZY(Y),ZX(X); int H = ZY.size(); int W = ZX.size(); int inf = 1000000; Dinic<int> di(H+W+2,0,inf); int S = H+W; int G = H+W+1; for(int i=0;i<H;++i) { di.make_edge(S,i,1); } for(int i=0;i<W;++i) { di.make_edge(i+H,G,1); } for(int i=0;i<n;++i) { int y = ZY.compressed[i]; int x = ZX.compressed[i]; di.make_edge(y,x+H,inf); } return di.maxflow(S,G); } /** * @url * @est */ int main() { cin.tie(0);ios::sync_with_stdio(false); int H,W; cin >> H >> W; int M = 500010; vector<vector<pair<int,int>>> vvp(M); for(int i=0;i<H;++i) { for(int j=0;j<W;++j) { int a; cin >> a; vvp[a].push_back({i,j}); } } int ans = 0; for(int n=1;n<M;++n) { if(vvp[n].empty()) continue; int cnt = solve(vvp[n]); ans += cnt; } cout << ans << endl; return 0; }