#983655 (C++17(gcc12)) No.3024 全単射的

提出ソース

結果

問題	No.3024 全単射的
ユーザー	👑 p-adic
提出日時	2024-05-26 12:04:15
言語	C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
結果	AC
実行時間	1,094 ms / 5,000 ms
コード長	27,455 bytes
コンパイル時間	14,786 ms
コンパイル使用メモリ	321,384 KB
最終ジャッジ日時	2025-02-21 16:44:00
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
other	AC * 22

権限があれば一括ダウンロードができます

コンパイルメッセージ

In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/specfun.h:45,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/cmath:1935,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:41,
                 from main.cpp:188:
In static member function 'static constexpr _Up* std::__copy_move<_IsMove, true, std::random_access_iterator_tag>::__copy_m(_Tp*, _Tp*, _Up*) [with _Tp = const int; _Up = int; bool _IsMove = false]',
    inlined from 'constexpr _OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove = false; _II = const int*; _OI = int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:501:30,
    inlined from 'constexpr _OI std::__copy_move_a1(_II, _II, _OI) [with bool _IsMove = false; _II = const int*; _OI = int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:528:42,
    inlined from 'constexpr _OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove = false; _II = const int*; _OI = int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:535:31,
    inlined from 'constexpr _OI std::copy(_II, _II, _OI) [with _II = const int*; _OI = int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_algobase.h:626:7,
    inlined from 'static _ForwardIterator std::__uninitialized_copy<true>::__uninit_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = const int*; _ForwardIterator = int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_uninitialized.h:147:27,
    inlined from '_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = const int*; _ForwardIterator = int*]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_uninitialized.h:185:15,
    inlined from 'constexp

ソースコード

raw source code

プレゼンテーションモードにする


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
#ifndef INCLUDE_MODE
  #define INCLUDE_MODE
  // #define REACTIVE
  // #define USE_GETLINE
#endif
#ifdef INCLUDE_MAIN
inline void Solve()
{
  CEXPR( int , bound_N , 1e5 ); CIN_ASSERT( N , 1 , bound_N );
  CEXPR( ll , bound_M , 1e18 ); CIN_ASSERT( M , 2 , bound_M );
  CIN_A( T2<ll> , 0 , N , LR );
  CoordinateCompress<ll> cc{};
  FOR( i , 0 , N ){
    auto& [Li,Ri] = LR[i];
    ASSERT( Li , 1 , M );
    ASSERT( Ri , Li + 1 , M );
    cc.SetL( --Li );
    cc.SetL( --Ri );
  }
  int N2 = cc.GetL() , N3 = N + N2;
  auto edge = [&]( const int& i ){
    vector<T2<int>> answer{};
    if( i < N ){
      auto& [Li,Ri] = LR[i];
      answer.push_back( { N + Li , 1 } );
      answer.push_back( { N + Ri , 1 } );
    } else if( i < N3 ){
      answer.push_back( { N3 + 1 , 1 } );
    } else if( i == N3 ){
      FOR( j , 0 , N ){
    answer.push_back( { j , 1 });
      }
    }
    return answer;
  };
  Graph graph{ N3 + 2 , edge };
  MaximumFlow mf{ graph , 0 };
  int answer = mf.GetFlow( N3 , N3 + 1 ).first;
  RETURN( answer );
}
REPEAT_MAIN(1);
#else // INCLUDE_MAIN
#ifdef INCLUDE_LIBRARY
// https://github.com/p-adic/cpp
// VVV ライブラリは以下に挿入する。
// 圧縮用
#define TE template
#define TY typename
#define US using
#define ST static
#define AS assert
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return 
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define LE length
#define PW Power
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&
#define VI virtual 
#define IS basic_istream<char,Traits>
#define OS basic_ostream<char,Traits>
#define ST_AS static_assert
#define reMO_CO remove_const
#define is_COructible_v is_constructible_v
#define rBE rbegin
#define reSZ resize
#ifdef DEBUG
  #include "C:/Users/user/Documents/Programming/Contest/Template/include/a_Body.hpp"
#else
// Random（1KB）
ll GetRand(CRI Rand_min,CRI Rand_max){AS(Rand_min <= Rand_max);ll AN = time(NULL);RE AN * rand()%(Rand_max + 1 - Rand_min)+ Rand_min;}
// Map (2KB)
#define DC_OF_HASH(...)struct hash<__VA_ARGS__>{IN size_t OP()(CO __VA_ARGS__& n)CO;};
CL is_ordered{PU:is_ordered()= delete;TE <TY T> ST CE auto Check(CO T& t)-> decltype(t < t,true_type());ST CE false_type Check(...);TE <TY T> ST CE 
    CO bool value = is_same_v< decltype(Check(declval<T>())),true_type >;};
TE <TY T>US Set = conditional_t<is_COructible_v<unordered_set<T>>,unordered_set<T>,conditional_t<is_ordered::value<T>,set<T>,VO>>;
#define DF_OF_AR_FOR_MAP(MAP,OPR)TE <TY T,TY U> IN MAP<T,U>& OP OPR ## =(MAP<T,U>& a,CO pair<T,U>& v){a[v.first]OPR ## = v.second;RE a;}TE <TY T,TY U
    > IN MAP<T,U>& OP OPR ## =(MAP<T,U>& a0,CO MAP<T,U>& a1){for(auto&[t,u]:a1){a0[t]OPR ## = u;}RE a0;}TE <TY T,TY U,TY ARG> IN MAP<T,U> OP OPR(MAP
    <T,U> a,CO ARG& arg){RE MO(a OPR ## = arg);}
#define DF_OF_ARS_FOR_MAP(MAP)DF_OF_AR_FOR_MAP(MAP,+);DF_OF_AR_FOR_MAP(MAP,-);DF_OF_AR_FOR_MAP(MAP,*);DF_OF_AR_FOR_MAP(MAP,/);DF_OF_AR_FOR_MAP(MAP,%
    );
TE <TY T,TY U>US Map = conditional_t<is_COructible_v<unordered_map<T,int>>,unordered_map<T,U>,conditional_t<is_ordered::value<T>,map<T,U>,VO>>;
DF_OF_ARS_FOR_MAP(map);DF_OF_ARS_FOR_MAP(unordered_map);
// Module (6KB)
#define DC_OF_CPOINT(POINT)IN CO U& POINT()CO NE
#define DC_OF_POINT(POINT)IN U& POINT()NE
#define DF_OF_CPOINT(POINT)TE <TY U> IN CO U& VirtualPointedSet<U>::POINT()CO NE{RE Point();}
#define DF_OF_POINT(POINT)TE <TY U> IN U& VirtualPointedSet<U>::POINT()NE{RE Point();}
TE <TY U>CL UnderlyingSet{PU:US type = U;};TE <TY U>CL VirtualPointedSet:VI PU UnderlyingSet<U>{PU:VI CO U& Point()CO NE = 0;VI U& Point()NE = 0
    ;DC_OF_CPOINT(Unit);DC_OF_CPOINT(Zero);DC_OF_CPOINT(One);DC_OF_CPOINT(Infty);DC_OF_POINT(init);DC_OF_POINT(root);};TE <TY U>CL PointedSet:VI PU 
    VirtualPointedSet<U>{PU:U m_b_U;IN PointedSet(U b_u = U());IN CO U& Point()CO NE;IN U& Point()NE;};TE <TY U>CL VirtualNSet:VI PU UnderlyingSet<U
    >{PU:VI U Transfer(CO U& u)= 0;IN U Inverse(CO U& u);};TE <TY U,TY F_U>CL AbstractNSet:VI PU VirtualNSet<U>{PU:F_U m_f_U;IN AbstractNSet(F_U f_U
    );IN AbstractNSet<U,F_U>& OP=(CO AbstractNSet&)NE;IN U Transfer(CO U& u);};TE <TY U>CL VirtualMagma:VI PU UnderlyingSet<U>{PU:VI U Product(U u0
    ,CO U& u1)= 0;IN U Sum(U u0,CO U& u1);};TE <TY U = ll>CL AdditiveMagma:VI PU VirtualMagma<U>{PU:IN U Product(U u0,CO U& u1);};TE <TY U = ll>CL 
    MultiplicativeMagma:VI PU VirtualMagma<U>{PU:IN U Product(U u0,CO U& u1);};TE <TY U,TY M_U>CL AbstractMagma:VI PU VirtualMagma<U>{PU:M_U m_m_U;IN 
    AbstractMagma(M_U m_U);IN AbstractMagma<U,M_U>& OP=(CO AbstractMagma<U,M_U>&)NE;IN U Product(U u0,CO U& u1);};
TE <TY U> IN PointedSet<U>::PointedSet(U b_U):m_b_U(MO(b_U)){}TE <TY U> IN CO U& PointedSet<U>::Point()CO NE{RE m_b_U;}TE <TY U> IN U& PointedSet<U
    >::Point()NE{RE m_b_U;}DF_OF_CPOINT(Unit);DF_OF_CPOINT(Zero);DF_OF_CPOINT(One);DF_OF_CPOINT(Infty);DF_OF_POINT(init);DF_OF_POINT(root);TE <TY U
    ,TY F_U> IN AbstractNSet<U,F_U>::AbstractNSet(F_U f_U):m_f_U(MO(f_U)){ST_AS(is_invocable_r_v<U,F_U,U>);}TE <TY U,TY F_U> IN AbstractNSet<U,F_U>& 
    AbstractNSet<U,F_U>::operator=(CO AbstractNSet<U,F_U>&)NE{RE *TH;}TE <TY U,TY F_U> IN U AbstractNSet<U,F_U>::Transfer(CO U& u){RE m_f_U(u);}TE 
    <TY U> IN U VirtualNSet<U>::Inverse(CO U& u){RE Transfer(u);}TE <TY U,TY M_U> IN AbstractMagma<U,M_U>::AbstractMagma(M_U m_U):m_m_U(MO(m_U
    )){ST_AS(is_invocable_r_v<U,M_U,U,U>);}TE <TY U,TY M_U> IN AbstractMagma<U,M_U>& AbstractMagma<U,M_U>::OP=(CO AbstractMagma<U,M_U>&)NE{RE *TH;}TE 
    <TY U> IN U AdditiveMagma<U>::Product(U u0,CO U& u1){RE MO(u0 += u1);}TE <TY U> IN U MultiplicativeMagma<U>::Product(U u0,CO U& u1){RE MO(u0 *= 
    u1);}TE <TY U,TY M_U> IN U AbstractMagma<U,M_U>::Product(U u0,CO U& u1){RE m_m_U(MO(u0),u1);}TE <TY U> IN U VirtualMagma<U>::Sum(U u0,CO U& u1
    ){RE Product(MO(u0),u1);}
TE <TY U>CL VirtualMonoid:VI PU VirtualMagma<U>,VI PU VirtualPointedSet<U>{};TE <TY U = ll>CL AdditiveMonoid:VI PU VirtualMonoid<U>,PU AdditiveMagma
    <U>,PU PointedSet<U>{};TE <TY U = ll>CL MultiplicativeMonoid:VI PU VirtualMonoid<U>,PU MultiplicativeMagma<U>,PU PointedSet<U>{PU:IN 
    MultiplicativeMonoid(U e_U);};TE <TY U,TY M_U>CL AbstractMonoid:VI PU VirtualMonoid<U>,PU AbstractMagma<U,M_U>,PU PointedSet<U>{PU:IN 
    AbstractMonoid(M_U m_U,U e_U);};
TE <TY U> IN MultiplicativeMonoid<U>::MultiplicativeMonoid(U e_U):PointedSet<U>(MO(e_U)){}TE <TY U,TY M_U> IN AbstractMonoid<U,M_U>::AbstractMonoid
    (M_U m_U,U e_U):AbstractMagma<U,M_U>(MO(m_U)),PointedSet<U>(MO(e_U)){}
TE <TY U>CL VirtualGroup:VI PU VirtualMonoid<U>,VI PU VirtualPointedSet<U>,VI PU VirtualNSet<U>{};TE <TY U = ll>CL AdditiveGroup:VI PU VirtualGroup<U
    >,PU AdditiveMonoid<U>{PU:IN U Transfer(CO U& u);};TE <TY U,TY M_U,TY I_U>CL AbstractGroup:VI PU VirtualGroup<U>,PU AbstractMonoid<U,M_U>,PU 
    AbstractNSet<U,I_U>{PU:IN AbstractGroup(M_U m_U,U e_U,I_U i_U);};
TE <TY U,TY M_U,TY I_U> IN AbstractGroup<U,M_U,I_U>::AbstractGroup(M_U m_U,U e_U,I_U i_U):AbstractMonoid<U,M_U>(MO(m_U),MO(e_U)),AbstractNSet<U,I_U
    >(MO(i_U)){}TE <TY U> IN U AdditiveGroup<U>::Transfer(CO U& u){RE -u;}
TE <TY R,TY U>CL VirtualRSet:VI PU UnderlyingSet<U>{PU:VI U Action(CO R& r,U u)= 0;IN U PW(U u,CO R& r);IN U ScalarProduct(CO R& r,U u);};TE <TY U,TY 
    MAGMA>CL RegularRSet:VI PU VirtualRSet<U,U>,PU MAGMA{PU:IN RegularRSet(MAGMA magma);IN U Action(CO U& r,U u);};TE <TY MAGMA> RegularRSet(MAGMA 
    magma)-> RegularRSet<inner_t<MAGMA>,MAGMA>;TE <TY R,TY U,TY O_U>CL AbstractRSet:VI PU VirtualRSet<R,U>{PU:O_U m_o_U;IN AbstractRSet(CO R& dummy0
    ,CO U& dummy1,O_U o_U);IN AbstractRSet<R,U,O_U>& OP=(CO AbstractRSet<R,U,O_U>&)NE;IN U Action(CO R& r,U u);};TE <TY R,TY U,TY O_U,TY GROUP>CL 
    AbstractModule:PU AbstractRSet<R,U,O_U>,PU GROUP{PU:IN AbstractModule(CO R& dummy,O_U o_U,GROUP M);};TE <TY R,TY O_U,TY GROUP> AbstractModule(CO 
    R& dummy,O_U o_U,GROUP M)-> AbstractModule<R,inner_t<GROUP>,O_U,GROUP>;TE <TY R,TY U>CL Module:VI PU VirtualRSet<R,U>,PU AdditiveGroup<U>{PU:IN U 
    Action(CO R& r,U u);};
TE <TY R,TY MAGMA> IN RegularRSet<R,MAGMA>::RegularRSet(MAGMA magma):MAGMA(MO(magma)){}TE <TY R,TY U,TY O_U> IN AbstractRSet<R,U,O_U>::AbstractRSet
    (CO R& dummy0,CO U& dummy1,O_U o_U):m_o_U(MO(o_U)){ST_AS(is_invocable_r_v<U,O_U,R,U>);}TE <TY R,TY U,TY O_U,TY GROUP> IN AbstractModule<R,U,O_U
    ,GROUP>::AbstractModule(CO R& dummy,O_U o_U,GROUP M):AbstractRSet<R,U,O_U>(dummy,M.One(),MO(o_U)),GROUP(MO(M)){ST_AS(is_same_v<U,inner_t<GROUP
    >>);}TE <TY R,TY U,TY O_U> IN AbstractRSet<R,U,O_U>& AbstractRSet<R,U,O_U>::OP=(CO AbstractRSet<R,U,O_U>&)NE{RE *TH;}TE <TY U,TY MAGMA> IN U 
    RegularRSet<U,MAGMA>::Action(CO U& r,U u){RE TH->Product(r,MO(u));}TE <TY R,TY U,TY O_U> IN U AbstractRSet<R,U,O_U>::Action(CO R& r,U u){RE m_o_U
    (r,MO(u));}TE <TY R,TY U> IN U Module<R,U>::Action(CO R& r,U u){RE MO(u *= r);}TE <TY R,TY U> IN U VirtualRSet<R,U>::PW(U u,CO R& r){RE Action(r
    ,MO(u));}TE <TY R,TY U> IN U VirtualRSet<R,U>::ScalarProduct(CO R& r,U u){RE Action(r,MO(u));}
// Graph (5KB)
TE <TY T,TY R1,TY R2,TY E>CL VirtualGraph:VI PU UnderlyingSet<T>{PU:VI R1 Enumeration(CRI i)= 0;IN R2 Enumeration_inv(CO T& t);TE <TY PATH> IN R2 
    Enumeration_inv(CO PATH& p);IN VO Reset();VI CRI SZ()CO NE = 0;VI E& edge()NE = 0;VI ret_t<E,T> Edge(CO T& t)= 0;TE <TY PATH> IN ret_t<E,T> Edge
    (CO PATH& p);ST IN CO T& Vertex(CO T& t)NE;TE <TY PATH> ST IN CO T& Vertex(CO PATH& e)NE;VI R2 Enumeration_inv_Body(CO T& t)= 0;};TE <TY T,TY R1
    ,TY R2,TY E>CL EdgeImplimentation:VI PU VirtualGraph<T,R1,R2,E>{PU:int m_SZ;E m_edge;IN EdgeImplimentation(CRI SZ,E edge);IN CRI SZ()CO NE;IN E& 
    edge()NE;IN ret_t<E,T> Edge(CO T& t);};TE <TY E>CL Graph:PU EdgeImplimentation<int,CRI,CRI,E>{PU:IN Graph(CRI SZ,E edge);IN CRI Enumeration(CRI i
    );TE <TY F> IN Graph<F> GetGraph(F edge)CO;IN CRI Enumeration_inv_Body(CRI t);};TE <TY T,TY Enum_T,TY Enum_T_inv,TY E>CL EnumerationGraph:PU 
    EdgeImplimentation<T,ret_t<Enum_T,int>,ret_t<Enum_T_inv,T>,E>{PU:Enum_T m_enum_T;Enum_T_inv m_enum_T_inv;IN EnumerationGraph(CRI SZ,Enum_T enum_T
    ,Enum_T_inv enum_T_inv,E edge);IN ret_t<Enum_T,int> Enumeration(CRI i);TE <TY F> IN EnumerationGraph<T,Enum_T,Enum_T_inv,F> GetGraph(F edge)CO;IN 
    ret_t<Enum_T_inv,T> Enumeration_inv_Body(CO T& t);};TE <TY Enum_T,TY Enum_T_inv,TY E> EnumerationGraph(CRI SZ,Enum_T enum_T,Enum_T_inv enum_T_inv
    ,E edge)-> EnumerationGraph<decldecay_t(declval<Enum_T>()(0)),Enum_T,Enum_T_inv,E>;TE <TY T,TY E>CL MemorisationGraph:PU EdgeImplimentation<T,T
    ,CRI,E>{PU:int m_LE;VE<T> m_memory;Map<T,int> m_memory_inv;IN MemorisationGraph(CRI SZ,CO T& dummy,E edge);IN T Enumeration(CRI i);IN VO Reset
    ();TE <TY F> IN MemorisationGraph<T,F> GetGraph(F edge)CO;IN CRI Enumeration_inv_Body(CO T& t);};
TE <TY T,TY R1,TY R2,TY E> IN EdgeImplimentation<T,R1,R2,E>::EdgeImplimentation(CRI SZ,E edge):m_SZ(SZ),m_edge(MO(edge)){ST_AS(is_COructible_v<T,R1> 
    && is_COructible_v<int,R2> && is_invocable_v<E,T>);}TE <TY E> IN Graph<E>::Graph(CRI SZ,E edge):EdgeImplimentation<int,CRI,CRI,E>(SZ,MO(edge
    )){}TE <TY T,TY Enum_T,TY Enum_T_inv,TY E> IN EnumerationGraph<T,Enum_T,Enum_T_inv,E>::EnumerationGraph(CRI SZ,Enum_T enum_T,Enum_T_inv 
    enum_T_inv,E edge):EdgeImplimentation<T,ret_t<Enum_T,int>,ret_t<Enum_T_inv,T>,E>(SZ,MO(edge)),m_enum_T(MO(enum_T)),m_enum_T_inv(MO(enum_T_inv
    )){}TE <TY T,TY E> IN MemorisationGraph<T,E>::MemorisationGraph(CRI SZ,CO T& dummy,E edge):EdgeImplimentation<T,T,CRI,E>(SZ,MO(edge)),m_LE
    (),m_memory(),m_memory_inv(){ST_AS(is_invocable_v<E,T>);}TE <TY E> IN CRI Graph<E>::Enumeration(CRI i){RE i;}TE <TY T,TY Enum_T,TY Enum_T_inv,TY 
    E> IN ret_t<Enum_T,int> EnumerationGraph<T,Enum_T,Enum_T_inv,E>::Enumeration(CRI i){RE m_enum_T(i);}TE <TY T,TY E> IN T MemorisationGraph<T,E
    >::Enumeration(CRI i){AS(0 <= i && i < m_LE);RE m_memory[i];}TE <TY T,TY R1,TY R2,TY E> IN R2 VirtualGraph<T,R1,R2,E>::Enumeration_inv(CO T& t
    ){RE Enumeration_inv_Body(t);}TE <TY T,TY R1,TY R2,TY E> TE <TY PATH> IN R2 VirtualGraph<T,R1,R2,E>::Enumeration_inv(CO PATH& p){RE 
    Enumeration_inv_Body(get<0>(p));}TE <TY E> IN CRI Graph<E>::Enumeration_inv_Body(CRI i){RE i;}TE <TY T,TY Enum_T,TY Enum_T_inv,TY E> IN ret_t
    <Enum_T_inv,T> EnumerationGraph<T,Enum_T,Enum_T_inv,E>::Enumeration_inv_Body(CO T& t){RE m_enum_T_inv(t);}TE <TY T,TY E> IN CRI MemorisationGraph
    <T,E>::Enumeration_inv_Body(CO T& t){if(m_memory_inv.count(t)== 0){AS(m_LE < TH->SZ());m_memory.push_back(t);RE m_memory_inv[t]= m_LE++;}RE 
    m_memory_inv[t];}TE <TY T,TY R1,TY R2,TY E> VO VirtualGraph<T,R1,R2,E>::Reset(){}TE <TY T,TY E> IN VO MemorisationGraph<T,E>::Reset(){m_LE = 0
    ;m_memory.clear();m_memory_inv.clear();}TE <TY T,TY R1,TY R2,TY E> IN CRI EdgeImplimentation<T,R1,R2,E>::SZ()CO NE{RE m_SZ;}TE <TY T,TY R1,TY R2
    ,TY E> IN E& EdgeImplimentation<T,R1,R2,E>::edge()NE{RE m_edge;}TE <TY T,TY R1,TY R2,TY E> IN ret_t<E,T> EdgeImplimentation<T,R1,R2,E>::Edge(CO 
    T& t){RE m_edge(t);}TE <TY T,TY R1,TY R2,TY E> TE <TY PATH> IN ret_t<E,T> VirtualGraph<T,R1,R2,E>::Edge(CO PATH& p){RE Edge(get<0>(p));}TE <TY E> 
    TE <TY F> IN Graph<F> Graph<E>::GetGraph(F edge)CO{RE Graph<F>(TH->SZ(),MO(edge));}TE <TY T,TY Enum_T,TY Enum_T_inv,TY E> TE <TY F> IN 
    EnumerationGraph<T,Enum_T,Enum_T_inv,F> EnumerationGraph<T,Enum_T,Enum_T_inv,E>::GetGraph(F edge)CO{RE EnumerationGraph<T,Enum_T,Enum_T_inv,F>(TH
    ->SZ(),m_enum_T,m_enum_T_inv,MO(edge));}TE <TY T,TY E> TE <TY F> IN MemorisationGraph<T,F> MemorisationGraph<T,E>::GetGraph(F edge)CO{RE 
    MemorisationGraph<T,F>(TH->SZ(),MO(edge));}TE <TY T,TY R1,TY R2,TY E> IN CO T& VirtualGraph<T,R1,R2,E>::Vertex(CO T& t)NE{RE t;}TE <TY T,TY R1,TY 
    R2,TY E> TE <TY PATH> IN CO T& VirtualGraph<T,R1,R2,E>::Vertex(CO PATH& e)NE{RE Vertex(get<0>(e));}
#endif
#ifdef DEBUG
  #include "c:/Users/user/Documents/Programming/Mathematics/SetTheory/DirectProduct/CoordinateCompress/a_Body.hpp"
#else
TE <TY INT = ll>CL CoordinateCompress{PU:set<INT> m_r;VE<INT*> m_l;IN CoordinateCompress();IN VO SetR(INT t);TE <TY U,TE <TY...> TY V > IN VO SetR(V
    <U> a);pair<VE<INT>,unordered_map<INT,int>> GetR();IN VO clearR();IN VO SetL(INT& t);TE <TY U,TE <TY...> TY V > IN VO SetL(V<U>& a);int GetL();IN 
    VO clearL();};
TE <TY INT> IN CoordinateCompress<INT>::CoordinateCompress():m_r(),m_l(){}TE <TY INT> IN VO CoordinateCompress<INT>::SetR(INT t){m_r.insert(MO(t
    ));}TE <TY INT> TE <TY U,TE <TY...> TY V > IN VO CoordinateCompress<INT>::SetR(V<U> a){for(auto& t:a){SetR(MO(t));}}TE <TY INT>pair<VE<INT
    >,unordered_map<INT,int>> CoordinateCompress<INT>::GetR(){pair<VE<INT>,unordered_map<INT,int>> AN{};AN.first.reSZ(m_r.SZ());int i = 0;for(auto t
    :m_r){AN.first[i]= t;AN.second[t]= i++;}RE AN;}TE <TY INT> IN VO CoordinateCompress<INT>::clearR(){m_r.clear();}TE <TY INT> IN VO 
    CoordinateCompress<INT>::SetL(INT& t){m_l.push_back(&t);}TE <TY INT> TE <TY U,TE <TY...> TY V > IN VO CoordinateCompress<INT>::SetL(V<U>& a){for
    (auto& t:a){SetL(t);}}TE <TY INT>int CoordinateCompress<INT>::GetL(){int i = -1;if(!m_l.empty()){auto comp =[](INT* CO& p0,INT* CO& p1){RE *p0 < 
    *p1;};sort(m_l.BE(),m_l.end(),comp);INT temp = *(m_l[0])- 1;for(auto p:m_l){*p = temp == *p?i:(temp = *p,++i);}}RE ++i;}TE <TY INT> IN VO 
    CoordinateCompress<INT>::clearL(){m_l.clear();}
#endif
#ifdef DEBUG
  #include "c:/Users/user/Documents/Programming/Mathematics/Geometry/Graph/MaximumFlow/a_Body.hpp"
#else
TE <TY T,TY GRAPH,TY U,TY ABEL_GROUP>CL AbstractMaximumFlow{PU:GRAPH& m_G;ABEL_GROUP m_M;IN AbstractMaximumFlow(GRAPH& G,ABEL_GROUP M);pair<U,VE<VE
    <tuple<T,U>>>> GetFlow(CO T& t_start,CO T& t_final);};TE <TY GRAPH,TY ABEL_GROUP> AbstractMaximumFlow(GRAPH& G,ABEL_GROUP M)-> 
    AbstractMaximumFlow<inner_t<GRAPH>,GRAPH,inner_t<ABEL_GROUP>,ABEL_GROUP>;TE <TY T,TY GRAPH,TY U>CL MaximumFlow:PU AbstractMaximumFlow<T,GRAPH,U
    ,AdditiveGroup<U>>{PU:IN MaximumFlow(GRAPH& G,CO U& dummy);};TE <TY GRAPH,TY U> MaximumFlow(GRAPH& G,CO U& dummy)-> MaximumFlow<inner_t<GRAPH
    >,GRAPH,U>;
TE <TY T,TY GRAPH,TY U,TY ABEL_GROUP> IN AbstractMaximumFlow<T,GRAPH,U,ABEL_GROUP>::AbstractMaximumFlow(GRAPH& G,ABEL_GROUP M):m_G(G),m_M(MO(M)){}TE 
    <TY T,TY GRAPH,TY U> IN MaximumFlow<T,GRAPH,U>::MaximumFlow(GRAPH& G,CO U& dummy):AbstractMaximumFlow<T,GRAPH,U,AdditiveGroup<U>>(G,AdditiveGroup
    <U>()){}TE <TY T,TY GRAPH,TY U,TY ABEL_GROUP>pair<U,VE<VE<tuple<T,U>>>> AbstractMaximumFlow<T,GRAPH,U,ABEL_GROUP>::GetFlow(CO T& t_start,CO T& 
    t_final){CO U& zero = m_M.Zero();CRI SZ = m_G.SZ();VE<VE<tuple<int,U,int,int>>> rest(SZ);VE<VE<tuple<T,U>>> flow(SZ);for(int i = 0;i < SZ;i
    ++){auto&& vi = m_G.Enumeration(i);for(auto&[vj,fj]:m_G.Edge(vi)){AS(vi != vj && !(fj < zero));if(zero < fj){auto&& j = m_G.Enumeration_inv(vj
    );rest[i].push_back({j,fj,rest[j].SZ(),flow[i].SZ()});rest[j].push_back({i,zero,rest[i].SZ()- 1,-1});flow[i].push_back({vj,zero});}}}VE<int> 
    edge_num_max(SZ);for(int i = 0;i < SZ;i++){edge_num_max[i]= rest[i].SZ()- 1;}auto&& i_start = m_G.Enumeration_inv(t_start);auto&& i_final = m_G
    .Enumeration_inv(t_final);U flow_sum = zero;bool updated = true;for(int LE = 1;LE < SZ && updated;LE++){updated = false;LI<int> bfs ={i_start};VE
    <int> distance = VE(SZ,-1);distance[i_start]= 0;WH(!bfs.empty()){CO int i = bfs.back();bfs.pop_back();for(auto& e:rest[i]){auto& j = get<0>(e);if
    (distance[j]== -1 && zero < get<1>(e)){distance[j]= distance[i]+ 1;bfs.push_front(j);}}}if(distance[i_final]== -1){break;}VE<int> path{i_start}
    ;auto edge_num = edge_num_max;WH(true){CO int i = path.back();WH(edge_num[i]>= 0){auto& rest_i_curr = rest[i][edge_num[i]];auto& j = get<0
    >(rest_i_curr);if(distance[i]+ 1 == distance[j]&& zero < get<1>(rest_i_curr)){path.push_back(j);break;}else{edge_num[i]--;}}if(edge_num[i]>= 0
    ){continue;}path.pop_back();if(i == i_start){break;}else if(i != i_final){edge_num[path.back()]--;}else{updated = true;auto IT = path.BE(),EN = 
    path.EN();U f_min = get<1>(rest[*IT][edge_num[*IT]]);WH(++IT != EN){f_min = min(f_min,get<1>(rest[*IT][edge_num[*IT]]));}flow_sum = m_M.Sum(MO
    (flow_sum),f_min);CO U f_min_inv = m_M.Inverse(f_min);for(auto& s:path){auto&[t,f_rest,rev_num,flow_num_s]= rest[s][edge_num[s]];auto&[s_copy
    ,f_rest_rev,edge_num_s_copy,flow_num_t]= rest[t][rev_num];if(flow_num_s >= 0){U& f_curr = get<1>(flow[s][flow_num_s]);f_curr = m_M.Sum(MO(f_curr
    ),f_min);}else{U& f_curr = get<1>(flow[t][flow_num_t]);AS(!((f_curr = m_M.Sum(MO(f_curr),f_min_inv))< zero));}f_rest = m_M.Sum(MO(f_rest
    ),f_min_inv);f_rest_rev = m_M.Sum(MO(f_rest_rev),f_min);}path ={i_start};}}}RE{MO(flow_sum),MO(flow)};}
#endif
// AAA ライブラリは以上に挿入する。
#define INCLUDE_MAIN
#include __FILE__
#else // INCLUDE_LIBRARY
#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE2 )
  #define SIGNAL signal( SIGABRT , &AlertAbort );
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) 
      ); assert( ( MIN ) <= A && A <= ( MAX ) )
  #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl
  #define COUT( ... ) VariadicCout( cout << "出力： " , __VA_ARGS__ ) << endl
  #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl
  #define COUT_A( A , N ) cout << "出力： "; OUTPUT_ARRAY( cout , A , N ) << endl
  #define CERR_ITR( A ) OUTPUT_ITR( cerr , A ) << endl
  #define COUT_ITR( A ) cout << "出力： "; OUTPUT_ITR( cout , A ) << endl
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize ( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define SIGNAL 
  #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE1 )
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
  #define CERR( ... ) 
  #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL
  #define CERR_A( N , A ) 
  #define COUT_A( N , A ) OUTPUT_ARRAY( cout , N , A ) << ENDL
  #define CERR_ITR( A ) 
  #define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << ENDL
#endif
#ifdef REACTIVE
  #define ENDL endl
#else
  #define ENDL "\n"
#endif
#ifdef USE_GETLINE
  #define SET_LL( A ) { GETLINE( A ## _str ); A = stoll( A ## _str ); }
  #define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ )
  #define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ )
#else
  #define SET_LL( A ) cin >> A
  #define CIN( LL , ... ) LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ )
  #define SET_A( I , N , ... ) VariadicResize( N + I , __VA_ARGS__ ); FOR( VARIABLE_FOR_SET_A , 0 , N ){ VariadicSet( cin , VARIABLE_FOR_SET_A + I , 
      __VA_ARGS__ ); }
  #define CIN_A( LL , I , N , ... ) VE<LL> __VA_ARGS__; SET_A( I , N , __VA_ARGS__ );
#endif
#include <bits/stdc++.h>
using namespace std;
#define REPEAT_MAIN( BOUND ) int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); SIGNAL; CEXPR( int , bound_test_case_num , BOUND ); 
    int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ CERR( "テストケースの個数を入力してください。" ); SET_ASSERT( test_case_num , 1 , 
    bound_test_case_num ); } REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num 
    , ":" ); } Solve(); CERR( "" ); } }
#define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now()
#define CURRENT_TIME static_cast<double>( chrono::duration_cast<chrono::microseconds>( chrono::system_clock::now() - watch ).count() / 1000.0 )
#define CHECK_WATCH( TL_MS ) ( CURRENT_TIME < TL_MS - 100.0 )
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define SET_ASSERT( A , MIN , MAX ) SET_LL( A ); ASSERT( A , MIN , MAX )
#define SET_A_ASSERT( I , N , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_A , 0 , N ){ SET_ASSERT( A[VARIABLE_FOR_SET_A + I] , MIN , MAX ); }
#define CIN_ASSERT( A , MIN , MAX ) decldecay_t( MAX ) A; SET_ASSERT( A , MIN , MAX )
#define CIN_A_ASSERT( I , N , A , MIN , MAX ) vector<decldecay_t( MAX )> A( N + I ); SET_A_ASSERT( I , N , A , MIN , MAX )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( decldecay_t( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( decldecay_t( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( decldecay_t( INITIAL ) VAR = INITIAL ; VAR + 1 > FINAL ; VAR -- )
#define ITR( ARRAY ) auto begin_ ## ARRAY = ARRAY .BE() , itr_ ## ARRAY = begin_ ## ARRAY , end_ ## ARRAY = ARRAY .EN()
#define FOR_ITR( ARRAY ) for( ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ )
#define RUN( VAR , ARRAY ) for( auto&& VAR : ARRAY )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS )
#define RETURN( ... ) COUT( __VA_ARGS__ ); return
// 型のエイリアス
#define decldecay_t( VAR ) decay_t<decltype( VAR )>
template <typename F , typename...Args> using ret_t = decltype( declval<F>()( declval<Args>()... ) );
template <typename T> using inner_t = typename T::type;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using lld = __float128;
template <typename INT> using T2 = pair<INT,INT>;
template <typename INT> using T3 = tuple<INT,INT,INT>;
template <typename INT> using T4 = tuple<INT,INT,INT,INT>;
using path = pair<int,ll>;
// 入出力用
template <class Traits , typename T , typename U , template <typename...> typename V> inline auto operator>>( basic_istream<char,Traits>& is , V<T,U
    >& arg ) -> decltype((get<0>(arg),is))& { return is >> get<0>( arg ) >> get<1>( arg ); }
template <class Traits , typename T , typename U , typename V> inline basic_istream<char,Traits>& operator>>( basic_istream<char,Traits>& is , tuple
    <T,U,V>& arg ) { return is >> get<0>( arg ) >> get<1>( arg ) >> get<2>( arg ); }
template <class Traits , typename T , typename U , typename V , typename W> inline basic_istream<char,Traits>& operator>>( basic_istream<char,Traits
    >& is , tuple<T,U,V,W>& arg ) { return is >> get<0>( arg ) >> get<1>( arg ) >> get<2>( arg ) >> get<3>( arg ); }
template <class Traits , typename T , typename U , template <typename...> typename V> inline auto operator<<( basic_ostream<char,Traits>& os , const 
    V<T,U>& arg ) -> decltype((get<0>(arg),os))& { return os << get<0>( arg ) << " " << get<1>( arg ); }
template <class Traits , typename T , typename U , typename V> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const 
    tuple<T,U,V>& arg ) { return os << get<0>( arg ) << " " << get<1>( arg ) << " " << get<2>( arg ); }
template <class Traits , typename T , typename U , typename V , typename W> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits
    >& os , const tuple<T,U,V,W>& arg ) { return os << get<0>( arg ) << " " << get<1>( arg ) << " " << get<2>( arg ) << " " << get<3>( arg ); }
#define DEFINITION_OF_COUT_FOR_VECTOR( V ) template <class Traits , typename Arg> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char
    ,Traits>& os , const V<Arg>& arg ) { auto begin = arg.begin() , end = arg.end(); auto itr = begin; while( itr != end ){ ( itr == begin ? os : os 
    << " " ) << *itr; itr++; } return os; }
DEFINITION_OF_COUT_FOR_VECTOR( vector );
DEFINITION_OF_COUT_FOR_VECTOR( list );
DEFINITION_OF_COUT_FOR_VECTOR( set );
DEFINITION_OF_COUT_FOR_VECTOR( unordered_set );
inline void VariadicResize( const int& size ) {}
template <typename Arg , typename... ARGS> inline void VariadicResize( const int& size , Arg& arg , ARGS&... args ) { arg.resize( size ); 
    VariadicResize( size , args... ); }
template <class Traits> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is , Arg& arg , 
    ARGS&... args ) { return VariadicCin( is >> arg , args... ); }
template <class Traits> inline basic_istream<char,Traits>& VariadicSet( basic_istream<char,Traits>& is , const int& i ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicSet( basic_istream<char,Traits>& is , const int& 
    i , Arg& arg , ARGS&... args ) { return VariadicSet( is >> arg[i] , i , args... ); }
template <class Traits> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const 
    char& separator , Arg& arg , ARGS&... args ) { return VariadicGetline( getline( is , arg , separator ) , separator , args... ); }
template <class Traits , typename Arg> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg& arg ) { return os 
    << arg; }
template <class Traits , typename Arg1 , typename Arg2 , typename... ARGS> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits
    >& os , const Arg1& arg1 , const Arg2& arg2 , const ARGS&... args ) { return VariadicCout( os << arg1 << " " , arg2 , args... ); }
// デバッグ用
#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( 
      "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
#endif
#define INCLUDE_LIBRARY
#include __FILE__
#endif // INCLUDE_LIBRARY
#endif // INCLUDE_MAIN
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

yukicoder

結果

コンパイルメッセージ

ソースコード