結果
問題 | No.1479 Matrix Eraser |
ユーザー | yuruhiya |
提出日時 | 2021-04-20 17:19:23 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 360 ms / 3,000 ms |
コード長 | 27,102 bytes |
コンパイル時間 | 2,682 ms |
コンパイル使用メモリ | 236,864 KB |
実行使用メモリ | 49,116 KB |
最終ジャッジ日時 | 2024-07-04 05:22:50 |
合計ジャッジ時間 | 9,672 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 25 ms
8,576 KB |
testcase_08 | AC | 48 ms
12,224 KB |
testcase_09 | AC | 118 ms
21,920 KB |
testcase_10 | AC | 265 ms
37,036 KB |
testcase_11 | AC | 154 ms
25,104 KB |
testcase_12 | AC | 32 ms
9,820 KB |
testcase_13 | AC | 49 ms
12,368 KB |
testcase_14 | AC | 33 ms
10,368 KB |
testcase_15 | AC | 7 ms
6,940 KB |
testcase_16 | AC | 38 ms
11,280 KB |
testcase_17 | AC | 349 ms
43,388 KB |
testcase_18 | AC | 356 ms
43,356 KB |
testcase_19 | AC | 330 ms
43,308 KB |
testcase_20 | AC | 358 ms
43,448 KB |
testcase_21 | AC | 360 ms
43,544 KB |
testcase_22 | AC | 355 ms
43,468 KB |
testcase_23 | AC | 334 ms
43,348 KB |
testcase_24 | AC | 354 ms
43,276 KB |
testcase_25 | AC | 358 ms
43,304 KB |
testcase_26 | AC | 351 ms
43,524 KB |
testcase_27 | AC | 106 ms
12,580 KB |
testcase_28 | AC | 107 ms
12,672 KB |
testcase_29 | AC | 104 ms
12,664 KB |
testcase_30 | AC | 107 ms
12,568 KB |
testcase_31 | AC | 110 ms
12,668 KB |
testcase_32 | AC | 48 ms
9,544 KB |
testcase_33 | AC | 49 ms
9,420 KB |
testcase_34 | AC | 48 ms
9,420 KB |
testcase_35 | AC | 50 ms
9,544 KB |
testcase_36 | AC | 50 ms
9,532 KB |
testcase_37 | AC | 8 ms
8,120 KB |
testcase_38 | AC | 111 ms
23,888 KB |
testcase_39 | AC | 237 ms
49,116 KB |
testcase_40 | AC | 1 ms
6,944 KB |
ソースコード
#line 2 "/home/yuruhiya/programming/library/Utility/get_MOD.cpp" constexpr long long get_MOD(){ #ifdef SET_MOD return SET_MOD; #else return 1000000007; #endif } #line 3 "/home/yuruhiya/programming/library/Utility/constants.cpp" #include<vector> #include<string> #include<utility> #include<queue> #define rep(i,n)for(int i=0;i<(n);++i) #define FOR(i,m,n)for(int i=(m);i<(n);++i) #define rrep(i,n)for(int i=(n)-1;i>=0;--i) #define rfor(i,m,n)for(int i=(m);i>=(n);--i) #define INTERNAL_CAT_IMPL(s1,s2)s1##s2 #define INTERNAL_CAT(s1,s2)INTERNAL_CAT_IMPL(s1,s2) #ifdef __COUNTER__ #define loop(n)rep(INTERNAL_CAT(_i,__COUNTER__),n) #else #define loop(n)rep(INTERNAL_CAT(_i,__COUNTER__),n) #endif #define unless(c)if(!(c)) #define ALL(x)(x).begin(),(x).end() #define RALL(x)(x).rbegin(),(x).rend() #define range_it(a,l,r)(a).begin()+(l),(a).begin()+(r) using ll=long long;using LD=long double;using VB=std::vector<bool>;using VVB=std::vector<VB>;using VI=std::vector<int>;using VVI=std::vector<VI>;using VL=std::vector<ll>;using VVL=std::vector<VL>;using VS=std::vector<std::string>;using VD=std::vector<LD>;using PII=std::pair<int,int>;using VP=std::vector<PII>;using PLL=std::pair<ll,ll>;using VPL=std::vector<PLL>;template<class T>using PQ=std::priority_queue<T>;template<class T>using PQS=std::priority_queue<T,std::vector<T>,std::greater<T>>;constexpr int inf=1000000000;constexpr long long inf_ll=1000000000000000000ll,MOD=get_MOD();constexpr long double PI=3.14159265358979323846,tau=PI*2,EPS=1e-12; #line 2 "/home/yuruhiya/programming/library/Utility/Scanner.cpp" #include<iostream> #line 6 "/home/yuruhiya/programming/library/Utility/Scanner.cpp" #include<tuple> #include<type_traits> #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #define putchar_unlocked _putchar_nolock #define fwrite_unlocked fwrite #define fflush_unlocked fflush #endif class Scanner{template<class T,class=void>struct has_scan : std::false_type{};template<class T>struct has_scan<T,std::void_t<decltype(std::declval<T>().template scan<Scanner>())>>: std::true_type{};public:static int gc(){return getchar_unlocked();}static char next_char(){char c;scan(c);return c;}template<class T>static void scan(T&v){if(has_scan<T>::value){v.template scan<Scanner>();}else{std::cin>>v;}}static void scan(char&v){while(std::isspace(v=gc()));}static void scan(bool&v){v=next_char()!='0';}static void scan(std::vector<bool>::reference v){bool b;scan(b);v=b;}static void scan(std::string&v){v.clear();for(char c=next_char();!std::isspace(c);c=gc())v+=c;}static void scan(int&v){v=0;bool neg=false;char c=next_char();if(c=='-'){neg=true;c=gc();}for(;std::isdigit(c);c=gc())v=v*10+(c-'0');if(neg)v=-v;}static void scan(long long&v){v=0;bool neg=false;char c=next_char();if(c=='-'){neg=true;c=gc();}for(;std::isdigit(c);c=gc())v=v*10+(c-'0');if(neg)v=-v;}static void scan(double&v){v=0;double dp=1;bool neg=false,after_dp=false;char c=next_char();if(c=='-'){neg=true;c=gc();}for(;std::isdigit(c)||c=='.';c=gc()){if(c=='.'){after_dp=true;}else if(after_dp){v+=(c-'0')*(dp*=0.1);}else{v=v*10+(c-'0');}}if(neg)v=-v;}static void scan(long double&v){v=0;long double dp=1;bool neg=false,after_dp=false;char c=next_char();if(c=='-'){neg=true;c=gc();}for(;std::isdigit(c)||c=='.';c=gc()){if(c=='.'){after_dp=true;}else if(after_dp){v+=(c-'0')*(dp*=0.1);}else{v=v*10+(c-'0');}}if(neg)v=-v;}template<class T,class U>static void scan(std::pair<T,U>&v){scan(v.first);scan(v.second);}template<class T,std::enable_if_t<!std::is_same_v<bool,T>,std::nullptr_t> =nullptr>static void scan(std::vector<T>&v){for(auto&e : v)scan(e);}template<class T,std::enable_if_t<std::is_same_v<bool,T>,std::nullptr_t> =nullptr>static void scan(std::vector<T>&v){for(auto e : v)scan(e);}private:template<std::size_t N=0,class T>static void scan_tuple_impl(T&v){if constexpr(N<std::tuple_size_v<T>){scan(std::get<N>(v));scan_tuple_impl<N+1>(v);}}public:template<class... T>static void scan(std::tuple<T...>&v){scan_tuple_impl(v);}private:struct Read2DVectorHelper{std::size_t h,w;Read2DVectorHelper(std::size_t _h,std::size_t _w): h(_h),w(_w){}template<class T>operator std::vector<std::vector<T>>(){std::vector vector(h,std::vector<T>(w));scan(vector);return vector;}};struct ReadVectorHelper{std::size_t n;ReadVectorHelper(std::size_t _n): n(_n){}template<class T>operator std::vector<T>(){std::vector<T>vector(n);scan(vector);return vector;}auto operator[](std::size_t m){return Read2DVectorHelper(n,m);}};public:template<class T>T read()const{T result;scan(result);return result;}template<class T>auto read(std::size_t n)const{std::vector<T>result(n);scan(result);return result;}template<class T>auto read(std::size_t h,std::size_t w)const{std::vector result(h,std::vector<T>(w));scan(result);return result;}std::string read_line()const{std::string v;for(char c=gc();c!='\n'&&c!='\0';c=gc())v+=c;return v;}template<class T>operator T()const{return read<T>();}int operator--(int)const{return read<int>()-1;}auto operator[](std::size_t n)const{return ReadVectorHelper(n);}auto operator[](const std::pair<std::size_t,std::size_t>&nm)const{return Read2DVectorHelper(nm.first,nm.second);}void operator()()const{}template<class H,class... T>void operator()(H&&h,T&&... t)const{scan(h);operator()(std::forward<T>(t)...);}private:template<template<class...>class,class...>struct Column;template<template<class...>class V,class Head,class... Tail>struct Column<V,Head,Tail...>{template<class... Args>using vec=V<std::vector<Head>,Args...>;using type=typename Column<vec,Tail...>::type;};template<template<class...>class V>struct Column<V>{using type=V<>;};template<class... T>using column_t=typename Column<std::tuple,T...>::type;template<std::size_t N=0,class T>void column_impl(T&t)const{if constexpr(N<std::tuple_size_v<T>){auto&vec=std::get<N>(t);using V=typename std::remove_reference_t<decltype(vec)>::value_type;vec.push_back(read<V>());column_impl<N+1>(t);}}public:template<class... T>auto column(std::size_t h)const{column_t<T...>result;while(h--)column_impl(result);return result;}}in; #define inputs(T,...)\ T __VA_ARGS__;\in(__VA_ARGS__) #define ini(...)inputs(int,__VA_ARGS__) #define inl(...)inputs(long long,__VA_ARGS__) #define ins(...)inputs(std::string,__VA_ARGS__) #line 5 "/home/yuruhiya/programming/library/Utility/Printer.cpp" #include<array> #line 7 "/home/yuruhiya/programming/library/Utility/Printer.cpp" #include<string_view> #include<optional> #include<charconv> #line 11 "/home/yuruhiya/programming/library/Utility/Printer.cpp" #include<cstring> #include<cassert> class Printer{public:struct BoolString{std::string_view t,f;BoolString(std::string_view _t,std::string_view _f): t(_t),f(_f){}};struct Separator{std::string_view div,sep,last;Separator(std::string_view _div,std::string_view _sep,std::string_view _last): div(_div),sep(_sep),last(_last){}};inline static const BoolString Yes{"Yes","No"},yes{"yes","no"},YES{"YES","NO"},Int{"1","0"},Possible{"Possible","Impossible"};inline static const Separator space{" "," ","\n"},no_space{"","","\n"},endl{"\n","\n","\n"},comma{",",",","\n"},no_endl{" "," ",""},sep_endl{" ","\n","\n"};BoolString bool_str{Yes};Separator separator{space};private:template<class T,class=void>struct has_print : std::false_type{};template<class T>struct has_print<T,std::void_t<decltype(std::declval<T>().print(std::declval<Printer>()))>>: std::true_type{};public:void print(int v)const{char buf[12]{};if(auto [ptr,e]=std::to_chars(std::begin(buf),std::end(buf),v);e==std::errc{}){print(std::string_view(buf,ptr-buf));}else{assert(false);}}void print(long long v)const{char buf[21]{};if(auto [ptr,e]=std::to_chars(std::begin(buf),std::end(buf),v);e==std::errc{}){print(std::string_view(buf,ptr-buf));}else{assert(false);}}void print(bool v)const{print(v ? bool_str.t : bool_str.f);}void print(std::vector<bool>::reference v)const{print(v ? bool_str.t : bool_str.f);}void print(char v)const{putchar_unlocked(v);}void print(std::string_view v)const{fwrite_unlocked(v.data(),sizeof(std::string_view::value_type),v.size(),stdout);}void print(double v)const{std::printf("%.20f",v);}void print(long double v)const{std::printf("%.20Lf",v);}template<class T,std::enable_if_t<has_print<T>::value,std::nullptr_t> =nullptr>void print(const T&v)const{v.print(*this);}template<class T,std::enable_if_t<!has_print<T>::value,std::nullptr_t> =nullptr>void print(const T&v)const{std::cout<<v;}template<class T,class U>void print(const std::pair<T,U>&v)const{print(v.first);print(separator.div);print(v.second);}template<class T>void print(const std::optional<T>&v)const{print(*v);}template<class InputIterater>void print_range(const InputIterater&begin,const InputIterater&end)const{for(InputIterater i=begin;i!=end;++i){if(i!=begin)print(separator.sep);print(*i);}}template<class T>void print(const std::vector<T>&v)const{print_range(v.begin(),v.end());}template<class T,std::size_t N>void print(const std::array<T,N>&v)const{print_range(v.begin(),v.end());}template<class T>void print(const std::vector<std::vector<T>>&v)const{for(std::size_t i=0;i<v.size();++i){if(i)print(separator.last);print(v[i]);}}Printer()=default;Printer(const BoolString&_bool_str,const Separator&_separator): bool_str(_bool_str),separator(_separator){}Printer&operator()(){print(separator.last);return*this;}template<class Head>Printer&operator()(Head&&head){print(head);print(separator.last);return*this;}template<class Head,class... Tail>Printer&operator()(Head&&head,Tail&&... tail){print(head);print(separator.sep);return operator()(std::forward<Tail>(tail)...);}template<class... Args>Printer&flag(bool f,Args&&... args){if(f){return operator()(std::forward<Args>(args)...);}else{return*this;}}template<class InputIterator>Printer&range(const InputIterator&begin,const InputIterator&end){print_range(begin,end);print(separator.last);return*this;}template<class Container>Printer&range(const Container&a){range(a.begin(),a.end());return*this;}template<class... T>void exit(T&&... t){operator()(std::forward<T>(t)...);std::exit(EXIT_SUCCESS);}Printer&flush(){fflush_unlocked(stdout);return*this;}Printer&set(const BoolString&_bool_str){bool_str=_bool_str;return*this;}Printer&set(const Separator&_separator){separator=_separator;return*this;}Printer&set(std::string_view t,std::string_view f){bool_str=BoolString(t,f);return*this;}}out; #line 2 "/home/yuruhiya/programming/library/Utility/functions.cpp" #include<algorithm> #include<numeric> #include<cmath> #line 8 "/home/yuruhiya/programming/library/Utility/functions.cpp" template<class T=long long>constexpr T TEN(std::size_t n){T result=1;for(std::size_t i=0;i<n;++i)result*=10;return result;}template<class T,class U,std::enable_if_t<std::is_integral_v<T>&&std::is_integral_v<U>,std::nullptr_t> =nullptr>constexpr auto div_ceil(T n,U m){return(n+m-1)/m;}template<class T,class U>constexpr auto div_ceil2(T n,U m){return div_ceil(n,m)*m;}template<class T>constexpr T triangle(T n){return(n&1)?(n+1)/2*n : n/2*(n+1);}template<class T>constexpr T nC2(T n){return(n&1)?(n-1)/2*n : n/2*(n-1);}template<class T,class U>constexpr auto middle(const T&l,const U&r){return l+(r-l)/2;}template<class T,class U,class V>constexpr bool in_range(const T&v,const U&lower,const V&upper){return lower<=v&&v<upper;}template<class T,std::enable_if_t<std::is_integral_v<T>,std::nullptr_t> =nullptr>constexpr bool is_square(T n){T s=std::sqrt(n);return s*s==n||(s+1)*(s+1)==n;}template<class T=long long>constexpr T BIT(int b){return T(1)<<b;}template<class T>constexpr int BIT(T x,int i){return(x&(T(1)<<i))? 1 : 0;}template<class T>constexpr int Sgn(T x){return(0<x)-(0>x);}template<class T>bool is_leap(T year){return!(year%4)&&(year%100||!(year%400));}template<class T,class U,std::enable_if_t<std::is_integral_v<U>,std::nullptr_t> =nullptr>constexpr T Pow(T a,U n){assert(n>=0);T result=1;while(n>0){if(n&1){result*=a;n--;}else{a*=a;n>>=1;}}return result;}template<class T,class U,std::enable_if_t<std::is_integral_v<U>,std::nullptr_t> =nullptr>constexpr T Powmod(T a,U n,T mod){assert(n>=0);if(a>mod)a%=mod;T result=1;while(n>0){if(n&1){result=result*a%mod;n--;}else{a=a*a%mod;n>>=1;}}return result;}template<class T>bool chmax(T&a,const T&b){return a<b ? a=b,true : false;}template<class T>bool chmin(T&a,const T&b){return a>b ? a=b,true : false;}template<class T>int sz(const T&v){return v.size();}template<class T,class U>int lower_index(const T&a,const U&v){return std::lower_bound(a.begin(),a.end(),v)-a.begin();}template<class T,class U,class F>int lower_index(const T&a,const U&v,const F&f){return std::lower_bound(a.begin(),a.end(),v,f)-a.begin();}template<class T,class U>int upper_index(const T&a,const U&v){return std::upper_bound(a.begin(),a.end(),v)-a.begin();}template<class T,class U,class F>int upper_index(const T&a,const U&v,const F&f){return std::upper_bound(a.begin(),a.end(),v,f)-a.begin();}template<class T,class U=typename T::value_type>U Gcdv(const T&v){return std::accumulate(std::next(v.begin()),v.end(),U(*v.begin()),std::gcd<U,U>);}template<class T,class U=typename T::value_type>U Lcmv(const T&v){return std::accumulate(std::next(v.begin()),v.end(),U(*v.begin()),std::lcm<U,U>);}template<class T>T&Concat(T&v,const T&vec){v.insert(v.end(),vec.begin(),vec.end());return v;}namespace internal{template<class T,std::size_t N>auto make_vector(std::vector<int>&sizes,const T&init){if constexpr(N==1){return std::vector(sizes[0],init);}else{int size=sizes[N-1];sizes.pop_back();return std::vector(size,make_vector<T,N-1>(sizes,init));}}}template<class T,std::size_t N>auto make_vector(const int(&sizes)[N],const T&init=T()){std::vector s(std::rbegin(sizes),std::rend(sizes));return internal::make_vector<T,N>(s,init);}template<class F>struct rec_lambda{F f;rec_lambda(F&&f_): f(std::forward<F>(f_)){}template<class... Args>auto operator()(Args&&... args)const{return f(*this,std::forward<Args>(args)...);}};namespace lambda{auto char_to_int=[](char c){return c-'0';};auto lower_to_int=[](char c){return c-'a';};auto upper_to_int=[](char c){return c-'A';};auto int_to_char=[](int i)->char{return '0'+i;};auto int_to_lower=[](int i)->char{return 'a'+i;};auto int_to_upper=[](int i)->char{return 'A'+i;};auto is_odd=[](auto n){return n%2==1;};auto is_even=[](auto n){return n%2==0;};auto is_positive=[](auto n){return n>0;};auto is_negative=[](auto n){return n<0;};auto increment=[](auto n){return++n;};auto decrement=[](auto n){return--n;};auto self=[](const auto&n){return n;};auto first=[](const auto&n){return n.first;};auto second=[](const auto&n){return n.second;};template<class T>auto cast(){return [](const auto&n){return static_cast<T>(n);};};template<class T>auto equal_to(const T&x){return [x](auto y){return x==y;};}template<std::size_t I>auto get(){return [](const auto&n){return std::get<I>(n);};}template<class F>auto cmp(F&&f){return [f](const auto&a,const auto&b){return f(a)<f(b);};}} #line 6 "/home/yuruhiya/programming/library/template_no_Ruby.cpp" #if __has_include(<library/dump.hpp>) #include<library/dump.hpp> #define LOCAL #else #define dump(...)((void)0) #define dump2(...)((void)0) #endif #line 2 "/home/yuruhiya/programming/library/Utility/oj_local.cpp" template<class T>constexpr T oj_local(const T&oj,const T&local){ #ifndef LOCAL return oj; #else return local; #endif } #line 14 "/home/yuruhiya/programming/library/template_no_Ruby.cpp" #include<bits/stdc++.h> #line 6 "/home/yuruhiya/programming/library/Graph/BipartiteMatching.cpp" class BipartiteMatching{std::size_t left,right;std::vector<std::vector<int>>graph;std::vector<bool>used;std::vector<int>left_match,right_match;bool dfs(int v){if(used[v]){return false;}used[v]=true;for(int u : graph[v]){if(right_match[u]==-1||dfs(right_match[u])){left_match[v]=u;right_match[u]=v;return true;}}return false;}public:BipartiteMatching(std::size_t _left,std::size_t _right): left(_left),right(_right),graph(left),used(left),left_match(left),right_match(right){}BipartiteMatching(std::size_t _left,std::size_t _right,const std::vector<std::vector<int>>&_graph): left(_left),right(_right),graph(_graph),used(left),left_match(left),right_match(right){assert(graph.size()==left);}BipartiteMatching(std::size_t _left,std::size_t _right,const std::vector<std::pair<int,int>>&edges): left(_left),right(_right),graph(left),used(left),left_match(left),right_match(right){for(auto [u,v] : edges){graph[u].push_back(v);}}void add_edge(int l,int r){graph[l].push_back(r);}int solve(){int result=0;std::fill(left_match.begin(),left_match.end(),-1);std::fill(right_match.begin(),right_match.end(),-1);std::fill(used.begin(),used.end(),false);for(bool update=true;update;){update=false;for(std::size_t i=0;i<left;++i){if(left_match[i]==-1&&dfs(i)){update=true;++result;}}if(update){std::fill(used.begin(),used.end(),false);}}return result;}std::vector<std::pair<int,int>>edges()const{std::vector<std::pair<int,int>>result;for(std::size_t i=0;i<left;++i){if(left_match[i]!=-1){result.emplace_back(i,left_match[i]);}}return result;}}; #line 11 "/home/yuruhiya/programming/library/Utility/Point.cpp" struct Point{using direction_iterator=std::vector<Point>::const_iterator;private:static inline int W,H;public:static void set_range(int height,int width){H=height;W=width;}static int height(){return H;}static int width(){return W;}static constexpr Point zero(){return{0,0};}static constexpr Point L(){return{0,-1};}static constexpr Point R(){return{0,1};}static constexpr Point U(){return{-1,0};}static constexpr Point D(){return{1,0};}static constexpr Point LU(){return{-1,-1};}static constexpr Point LD(){return{1,-1};}static constexpr Point RU(){return{-1,1};}static constexpr Point RD(){return{1,1};}static const std::vector<Point>direction;int y,x;constexpr Point(): y(0),x(0){}constexpr Point(int _y,int _x): y(_y),x(_x){}constexpr Point(const std::pair<int,int>&yx): y(yx.first),x(yx.second){}Point(int n): y(n/W),x(n%W){}constexpr Point operator+()const{return*this;}constexpr Point operator-()const{return{-y,-x};}constexpr Point operator+(const Point&p)const{return Point(*this)+=p;}constexpr Point operator-(const Point&p)const{return Point(*this)-=p;}constexpr Point operator*(const Point&p)const{return Point(*this)*=p;}constexpr Point operator/(const Point&p)const{return Point(*this)/=p;}constexpr Point operator%(const Point&p)const{return Point(*this)%=p;}constexpr Point operator+(int n)const{return Point(*this)+=n;}constexpr Point operator-(int n)const{return Point(*this)-=n;}constexpr Point operator*(int n)const{return Point(*this)*=n;}constexpr Point operator/(int n)const{return Point(*this)/=n;}constexpr Point operator%(int n)const{return Point(*this)%=n;}constexpr Point&operator+=(const Point&p){y+=p.y;x+=p.x;return*this;}constexpr Point&operator-=(const Point&p){y-=p.y;x-=p.x;return*this;}constexpr Point&operator*=(const Point&p){y*=p.y;x*=p.x;return*this;}constexpr Point&operator/=(const Point&p){y/=p.y;x/=p.x;return*this;}constexpr Point&operator%=(const Point&p){y%=p.y;x%=p.x;return*this;}constexpr Point&operator+=(int n){y+=n;x+=n;return*this;}constexpr Point&operator-=(int n){y-=n;x-=n;return*this;}constexpr Point&operator*=(int n){y*=n;x*=n;return*this;}constexpr Point&operator/=(int n){y/=n;x/=n;return*this;}constexpr Point&operator%=(int n){y%=n;x%=n;return*this;}constexpr bool operator==(const Point&p)const{return y==p.y&&x==p.x;}constexpr bool operator!=(const Point&p)const{return y!=p.y||x!=p.x;}bool operator<(const Point&p)const{return to_i()<p.to_i();}bool operator<=(const Point&p)const{return to_i()<=p.to_i();}bool operator>(const Point&p)const{return to_i()>p.to_i();}bool operator>=(const Point&p)const{return to_i()>=p.to_i();}constexpr bool in_range(int height,int width)const{return 0<=y&&y<height&&0<=x&&x<width;}bool in_range()const{return in_range(H,W);}int to_i()const{return y*W+x;}constexpr Point yx()const{return{y,x};}constexpr std::pair<int,int>pair()const{return{y,x};}constexpr std::pair<int,int>anti_pair()const{return{x,y};}constexpr int manhattan(const Point&p)const{return std::abs(x-p.x)+std::abs(y-p.y);}constexpr int chebyshev(const Point&p)const{return std::max(std::abs(y-p.y),std::abs(x-p.x));}constexpr int distance_square(const Point&p)const{return(y-p.y)*(y-p.y)+(x-p.x)*(x-p.x);}template<class Real>constexpr Real distance(const Point&p)const{return std::sqrt(static_cast<Real>(distance_square(p)));}constexpr Point absolute(const Point&p)const{return absolute(*this-p);}constexpr Point absolute()const{return{std::abs(y),std::abs(x)};}class enumerate_adjacent_helper{std::shared_ptr<Point>p;direction_iterator first,last;class iterator{std::shared_ptr<Point>p;direction_iterator it;public:iterator(std::shared_ptr<Point>_p,direction_iterator _it): p(_p),it(_it){}Point operator*()const{return*p+*it;}iterator&operator++(){++it;return*this;}bool operator!=(iterator other)const{return it!=other.it;}};public:enumerate_adjacent_helper(std::shared_ptr<Point>_p,direction_iterator _first,direction_iterator _last): p(_p),first(_first),last(_last){}iterator begin()const{return iterator(p,first);}iterator end()const{return iterator(p,last);}};auto enumerate_adjacent(direction_iterator first,direction_iterator last)const{return enumerate_adjacent_helper(std::make_shared<Point>(*this),first,last);}auto adj4()const{return enumerate_adjacent(direction.begin()+1,direction.begin()+5);}auto adj4_and_this()const{return enumerate_adjacent(direction.begin(),direction.begin()+5);}auto adjacent8()const{return enumerate_adjacent(direction.begin()+1,direction.begin()+9);}auto adj8_and_this()const{return enumerate_adjacent(direction.begin(),direction.begin()+9);}class enumerate_adj_in_range_helper{std::shared_ptr<Point>p;direction_iterator first,last;class sentinel{};class iterator{std::shared_ptr<Point>p;direction_iterator first,last;void increment_until_in_range(){for(;first!=last;++first){if((*p+*first).in_range())return;}}public:iterator(std::shared_ptr<Point>_p,direction_iterator _first,direction_iterator _last): p(_p),first(_first),last(_last){increment_until_in_range();}Point operator*()const{return*p+*first;}iterator&operator++(){++first;increment_until_in_range();return*this;}bool operator!=([[maybe_unused]] sentinel other)const{return first!=last;}};public:enumerate_adj_in_range_helper(std::shared_ptr<Point>_p,direction_iterator _first,direction_iterator _last): p(_p),first(_first),last(_last){}iterator begin()const{return iterator(p,first,last);}sentinel end()const{return sentinel();}};template<class InputIterator>auto enumerate_adj_in_range(InputIterator first,InputIterator last)const{return enumerate_adj_in_range_helper(std::make_shared<Point>(*this),first,last);}auto adj4_in_range()const{return enumerate_adj_in_range(direction.begin()+1,direction.begin()+5);}auto adj4_and_this_in_range()const{return enumerate_adj_in_range(direction.begin(),direction.begin()+5);}auto adj8_in_range()const{return enumerate_adj_in_range(direction.begin()+1,direction.begin()+9);}auto ajd8_and_this_in_range()const{return enumerate_adj_in_range(direction.begin(),direction.begin()+9);}constexpr Point left()const{return{y,x-1};}constexpr Point right()const{return{y,x+1};}constexpr Point up()const{return{y-1,x};}constexpr Point down()const{return{y+1,x};}Point succ()const{if(x!=W-1){return{y,x+1};}else{return{y+1,0};}}Point pred()const{if(x!=0){return{y,x-1};}else{return{y-1,W-1};}}constexpr Point moved(char c)const{return Point(*this).move(c);}constexpr Point&move(char c){switch(c){case 'L':case 'l':case 'W':case '>':x--;break;case 'R':case 'r':case 'E':case '<':x++;break;case 'U':case 'u':case 'N':case '^':y--;break;case 'D':case 'd':case 'S':case 'v':y++;break;}return*this;}constexpr Point rotate90()const{return{-x,y};}constexpr Point rotate180()const{return{-y,-x};}constexpr Point rotate270()const{return{x,-y};}char to_direction_char(std::string_view lrud="LRUD")const{assert(4<=lrud.size()&&lrud.size()<=5);if(y==0&&x<0){return lrud[0];}else if(y==0&&x>0){return lrud[1];}else if(x==0&&y<0){return lrud[2];}else if(x==0&&y>0){return lrud[3];}else if(lrud.size()==5){return lrud[4];}else{assert(false);}}static Point to_direction(char c,std::string_view lrud="LRUD"){assert(lrud.size()==4);if(c==lrud[0]){return L();}else if(c==lrud[1]){return R();}else if(c==lrud[2]){return U();}else if(c==lrud[3]){return D();}else{return zero();}}static Point to_direction(std::string s,std::string_view lrud="LRUD"){if(s.size()==1){return to_direction(s[0],lrud);}else if(s.size()==2){Point p1=to_direction(s[0],lrud),p2=to_direction(s[1],lrud);assert((p1.x==0)^(p2.x==0));assert((p1.y==0)^(p2.y==0));return p1+p2;}else{assert(false);}}template<class T,class value_type=typename T::value_type::value_type>static std::optional<Point>find(const T&grid,const value_type&val){assert(static_cast<int>(grid.size())==H);for(int i=0;i<H;++i){assert(static_cast<int>(grid[i].size())==W);for(int j=0;j<W;++j){if(grid[i][j]==val){return Point(i,j);}}}return std::nullopt;}template<class T,class Predicate>static std::optional<Point>find_if(const T&grid,Predicate pred){assert(static_cast<int>(grid.size())==H);for(int i=0;i<H;++i){assert(static_cast<int>(grid[i].size())==W);for(int j=0;j<W;++j){if(pred(grid[i][j])){return Point(i,j);}}}return std::nullopt;}template<class T,class value_type=typename T::value_type::value_type>static std::optional<Point>find_one(const T&grid,const value_type&val){assert(static_cast<int>(grid.size())==H);std::optional<Point>result;for(int i=0;i<H;++i){assert(static_cast<int>(grid[i].size())==W);for(int j=0;j<W;++j){if(grid[i][j]==val){assert(!result);result=Point(i,j);}}}return result;}template<class T,class value_type=typename T::value_type::value_type>static std::vector<Point>find_all(const T&grid,const value_type&val){assert(static_cast<int>(grid.size())==H);std::vector<Point>result;for(int i=0;i<H;++i){assert(static_cast<int>(grid[i].size())==W);for(int j=0;j<W;++j){if(grid[i][j]==val){result.emplace_back(i,j);}}}return result;}static auto enumerate_2D_points(){class enumerate_2D_points_helper{public:class iterator{Point p;public:iterator(const Point&_p): p(_p){}Point operator*()const{return p;}iterator&operator++(){p=p.succ();return*this;}iterator&operator--(){p=p.pred();return*this;}bool operator!=(iterator other)const{return p!=other.p;}};iterator begin()const{return iterator(Point(0,0));}iterator end()const{return iterator(Point(H,0));}};return enumerate_2D_points_helper();}friend std::ostream&operator<<(std::ostream&os,const Point&p){return os<<'('<<p.y<<","<<p.x<<')';}friend std::istream&operator>>(std::istream&is,Point&p){return is>>p.y>>p.x;}};const std::vector<Point>Point::direction{Point::zero(),Point::R(),Point::D(),Point::U(),Point::L(),Point::RD(),Point::LU(),Point::RU(),Point::LD()}; #line 4 "a.cpp" using namespace std;int main(){int h=in,w=in;VVI a=in[h][w];map<int,vector<Point>>points_map;rep(i,h)rep(j,w){points_map[a[i][j]].emplace_back(i,j);}int l=0,r=0;VP edges;for(auto [val,points] : points_map){if(val==0)continue;map<int,int>row,column;for(Point p : points){int ll=row.count(p.y)? row[p.y] :(row[p.y]=l++);int rr=column.count(p.x)? column[p.x] :(column[p.x]=r++);edges.emplace_back(ll,rr);}}BipartiteMatching g(l,r,edges);out(g.solve());}