0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 am>..#include <s
0020: 73 74 72 65 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 stream>..#includ
0030: 65 20 3c 69 6f 6d 61 6e 69 70 3e 0d 0a 23 69 6e e <iomanip>..#in
0040: 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 3e 0d 0a clude <vector>..
0050: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 #include <string
0060: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 >..#include <map
0070: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 74 >..#include <set
0080: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 >..#include <alg
0090: 6f 72 69 74 68 6d 3e 0d 0a 23 69 6e 63 6c 75 64 orithm>..#includ
00a0: 65 20 3c 6e 75 6d 65 72 69 63 3e 0d 0a 23 69 6e e <numeric>..#in
00b0: 63 6c 75 64 65 20 3c 69 74 65 72 61 74 6f 72 3e clude <iterator>
00c0: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 66 75 6e 63 ..#include <func
00d0: 74 69 6f 6e 61 6c 3e 0d 0a 23 69 6e 63 6c 75 64 tional>..#includ
00e0: 65 20 3c 63 6f 6d 70 6c 65 78 3e 0d 0a 23 69 6e e <complex>..#in
00f0: 63 6c 75 64 65 20 3c 71 75 65 75 65 3e 0d 0a 23 clude <queue>..#
0100: 69 6e 63 6c 75 64 65 20 3c 73 74 61 63 6b 3e 0d include <stack>.
0110: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6d 61 74 68 .#include <cmath
0120: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 61 73 >..#include <cas
0130: 73 65 72 74 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 sert>..#include
0140: 3c 63 73 74 72 69 6e 67 3e 0d 0a 75 73 69 6e 67 <cstring>..using
0150: 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d namespace std;.
0160: 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f .typedef long lo
0170: 6e 67 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 ng LL;..typedef
0180: 63 6f 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 complex<double>
0190: 43 4d 50 3b 0d 0a 0d 0a 74 65 6d 70 6c 61 74 65 CMP;....template
01a0: 3c 74 79 70 65 6e 61 6d 65 20 56 3e 0d 0a 63 6c <typename V>..cl
01b0: 61 73 73 20 47 72 61 70 68 0d 0a 7b 0d 0a 09 6d ass Graph..{...m
01c0: 61 70 3c 56 2c 20 69 6e 74 3e 20 76 32 69 64 5f ap<V, int> v2id_
01d0: 3b 0d 0a 09 76 65 63 74 6f 72 3c 56 3e 20 20 20 ;...vector<V>
01e0: 69 64 32 76 5f 3b 0d 0a 70 75 62 6c 69 63 3a 0d id2v_;..public:.
01f0: 0a 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 ..vector< vector
0200: 3c 69 6e 74 3e 20 3e 20 47 3b 0d 0a 0d 0a 09 69 <int> > G;.....i
0210: 6e 74 20 76 65 72 74 28 20 63 6f 6e 73 74 20 56 nt vert( const V
0220: 26 20 74 20 29 0d 0a 09 7b 0d 0a 09 09 69 66 28 & t )...{....if(
0230: 20 21 76 32 69 64 5f 2e 63 6f 75 6e 74 28 74 29 !v2id_.count(t)
0240: 20 29 20 7b 20 76 32 69 64 5f 5b 74 5d 20 3d 20 ) { v2id_[t] =
0250: 47 2e 73 69 7a 65 28 29 3b 20 69 64 32 76 5f 2e G.size(); id2v_.
0260: 70 75 73 68 5f 62 61 63 6b 28 74 29 3b 20 47 2e push_back(t); G.
0270: 72 65 73 69 7a 65 28 47 2e 73 69 7a 65 28 29 2b resize(G.size()+
0280: 31 29 3b 20 7d 0d 0a 09 09 72 65 74 75 72 6e 20 1); }....return
0290: 76 32 69 64 5f 5b 74 5d 3b 0d 0a 09 7d 0d 0a 09 v2id_[t];...}...
02a0: 76 6f 69 64 20 65 64 67 65 28 20 63 6f 6e 73 74 void edge( const
02b0: 20 56 26 20 73 5f 2c 20 63 6f 6e 73 74 20 56 26 V& s_, const V&
02c0: 20 74 5f 20 29 0d 0a 09 7b 0d 0a 09 09 69 6e 74 t_ )...{....int
02d0: 20 73 3d 76 65 72 74 28 73 5f 29 2c 20 74 3d 76 s=vert(s_), t=v
02e0: 65 72 74 28 74 5f 29 3b 0d 0a 09 09 47 5b 73 5d ert(t_);....G[s]
02f0: 2e 70 75 73 68 5f 62 61 63 6b 28 74 29 3b 0d 0a .push_back(t);..
0300: 09 7d 0d 0a 09 63 6f 6e 73 74 20 56 26 20 6f 72 .}...const V& or
0310: 69 67 28 20 69 6e 74 20 76 20 29 0d 0a 09 7b 0d ig( int v )...{.
0320: 0a 09 09 72 65 74 75 72 6e 20 69 64 32 76 5f 5b ...return id2v_[
0330: 76 5d 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 63 v];...}..};....c
0340: 6c 61 73 73 20 53 74 72 6f 6e 67 6c 79 43 6f 6e lass StronglyCon
0350: 6e 65 63 74 65 64 43 6f 6d 70 6f 6e 65 6e 74 0d nectedComponent.
0360: 0a 7b 0d 0a 70 75 62 6c 69 63 3a 0d 0a 09 53 74 .{..public:...St
0370: 72 6f 6e 67 6c 79 43 6f 6e 6e 65 63 74 65 64 43 ronglyConnectedC
0380: 6f 6d 70 6f 6e 65 6e 74 28 20 63 6f 6e 73 74 20 omponent( const
0390: 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 69 vector< vector<i
03a0: 6e 74 3e 20 3e 26 20 47 20 29 0d 0a 09 09 3a 20 nt> >& G )....:
03b0: 73 63 63 28 29 2c 20 66 6f 72 65 73 74 28 29 2c scc(), forest(),
03c0: 20 47 28 47 29 2c 20 6e 6f 28 30 29 2c 20 64 66 G(G), no(0), df
03d0: 73 5f 6e 6f 28 47 2e 73 69 7a 65 28 29 29 2c 20 s_no(G.size()),
03e0: 64 66 73 5f 6c 6f 28 47 2e 73 69 7a 65 28 29 29 dfs_lo(G.size())
03f0: 2c 20 73 63 63 5f 69 64 28 47 2e 73 69 7a 65 28 , scc_id(G.size(
0400: 29 29 0d 0a 09 7b 0d 0a 09 09 66 6f 72 28 69 6e ))...{....for(in
0410: 74 20 76 3d 30 3b 20 76 3c 47 2e 73 69 7a 65 28 t v=0; v<G.size(
0420: 29 3b 20 2b 2b 76 29 0d 0a 09 09 09 64 66 73 28 ); ++v).....dfs(
0430: 76 29 3b 0d 0a 09 7d 0d 0a 0d 0a 09 76 65 63 74 v);...}.....vect
0440: 6f 72 3c 20 76 65 63 74 6f 72 3c 69 6e 74 3e 20 or< vector<int>
0450: 3e 20 73 63 63 3b 20 20 20 20 2f 2f 20 73 63 63 > scc; // scc
0460: 5b 69 5d 20 3a 20 74 68 65 20 6c 69 73 74 20 6f [i] : the list o
0470: 66 20 76 65 72 74 73 20 69 6e 20 74 68 65 20 69 f verts in the i
0480: 2d 74 68 20 63 6f 6d 70 6f 6e 65 6e 74 20 0d 0a -th component ..
0490: 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c .vector< vector<
04a0: 69 6e 74 3e 20 3e 20 66 6f 72 65 73 74 3b 20 2f int> > forest; /
04b0: 2f 20 74 68 65 20 66 6f 72 65 73 74 20 73 74 72 / the forest str
04c0: 75 63 74 75 72 65 20 6f 76 65 72 20 73 63 63 73 ucture over sccs
04d0: 0d 0a 0d 0a 70 72 69 76 61 74 65 3a 0d 0a 09 63 ....private:...c
04e0: 6f 6e 73 74 20 76 65 63 74 6f 72 3c 20 76 65 63 onst vector< vec
04f0: 74 6f 72 3c 69 6e 74 3e 20 3e 26 20 47 3b 0d 0a tor<int> >& G;..
0500: 09 69 6e 74 20 6e 6f 3b 0d 0a 09 76 65 63 74 6f .int no;...vecto
0510: 72 3c 69 6e 74 3e 20 64 66 73 5f 6e 6f 3b 20 2f r<int> dfs_no; /
0520: 2f 20 53 70 65 63 69 61 6c 3a 20 30 20 20 20 20 / Special: 0
0530: 20 20 20 3a 20 6e 6f 74 20 76 69 73 69 74 65 64 : not visited
0540: 20 79 65 74 0d 0a 09 76 65 63 74 6f 72 3c 69 6e yet...vector<in
0550: 74 3e 20 64 66 73 5f 6c 6f 3b 20 2f 2f 20 53 70 t> dfs_lo; // Sp
0560: 65 63 69 61 6c 3a 20 49 4e 54 5f 4d 41 58 20 3a ecial: INT_MAX :
0570: 20 61 6c 72 65 61 64 79 20 63 6c 61 73 73 69 66 already classif
0580: 69 65 64 20 69 6e 74 6f 20 73 6f 6d 65 20 73 63 ied into some sc
0590: 63 20 21 21 21 21 20 6e 6f 74 20 61 20 67 6f 6f c !!!! not a goo
05a0: 64 20 69 64 65 61 21 0d 0a 09 2f 2f 20 72 61 74 d idea!...// rat
05b0: 68 65 72 20 75 73 65 20 73 63 63 5f 69 64 20 66 her use scc_id f
05c0: 6f 72 20 74 68 61 74 20 70 75 72 70 6f 73 65 20 or that purpose
05d0: 28 64 69 73 74 69 6e 67 75 69 73 68 69 6e 67 20 (distinguishing
05e0: 61 73 73 69 67 6e 65 64 20 6f 72 20 6e 6f 74 29 assigned or not)
05f0: 0d 0a 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 73 ...vector<int> s
0600: 63 63 5f 69 64 3b 0d 0a 09 76 65 63 74 6f 72 3c cc_id;...vector<
0610: 69 6e 74 3e 20 70 65 6e 64 69 6e 67 3b 0d 0a 0d int> pending;...
0620: 0a 09 76 6f 69 64 20 64 66 73 28 69 6e 74 20 76 ..void dfs(int v
0630: 29 0d 0a 09 7b 0d 0a 09 09 69 66 28 20 64 66 73 )...{....if( dfs
0640: 5f 6e 6f 5b 76 5d 20 29 0d 0a 09 09 09 72 65 74 _no[v] ).....ret
0650: 75 72 6e 3b 0d 0a 0d 0a 09 09 64 66 73 5f 6e 6f urn;......dfs_no
0660: 5b 76 5d 20 3d 20 64 66 73 5f 6c 6f 5b 76 5d 20 [v] = dfs_lo[v]
0670: 3d 20 2b 2b 6e 6f 3b 20 20 20 20 2f 2f 20 76 69 = ++no; // vi
0680: 73 69 74 20 76 0d 0a 09 09 66 6f 72 28 69 6e 74 sit v....for(int
0690: 20 69 3d 30 3b 20 69 3c 47 5b 76 5d 2e 73 69 7a i=0; i<G[v].siz
06a0: 65 28 29 3b 20 2b 2b 69 29 20 2f 2f 20 76 69 73 e(); ++i) // vis
06b0: 69 74 20 63 68 69 6c 64 72 65 6e 0d 0a 09 09 7b it children....{
06c0: 0d 0a 09 09 09 69 6e 74 20 75 20 3d 20 47 5b 76 .....int u = G[v
06d0: 5d 5b 69 5d 3b 0d 0a 09 09 09 64 66 73 28 20 75 ][i];.....dfs( u
06e0: 20 29 3b 0d 0a 09 09 09 69 66 28 20 21 69 73 5f );.....if( !is_
06f0: 61 6c 72 65 61 64 79 5f 63 6c 61 73 73 69 66 69 already_classifi
0700: 65 64 5f 69 6e 5f 73 6f 6d 65 5f 73 63 63 28 75 ed_in_some_scc(u
0710: 29 20 29 0d 0a 09 09 09 09 64 66 73 5f 6c 6f 5b ) )......dfs_lo[
0720: 76 5d 20 3d 20 6d 69 6e 28 20 64 66 73 5f 6c 6f v] = min( dfs_lo
0730: 5b 76 5d 2c 20 64 66 73 5f 6c 6f 5b 47 5b 76 5d [v], dfs_lo[G[v]
0740: 5b 69 5d 5d 20 29 3b 0d 0a 09 09 7d 0d 0a 0d 0a [i]] );....}....
0750: 09 09 70 65 6e 64 69 6e 67 2e 70 75 73 68 5f 62 ..pending.push_b
0760: 61 63 6b 28 76 29 3b 0d 0a 09 09 69 66 28 20 64 ack(v);....if( d
0770: 66 73 5f 6e 6f 5b 76 5d 20 3d 3d 20 64 66 73 5f fs_no[v] == dfs_
0780: 6c 6f 5b 76 5d 20 29 20 7b 20 2f 2f 20 66 6f 75 lo[v] ) { // fou
0790: 6e 64 20 74 68 65 20 72 65 70 72 65 73 65 6e 74 nd the represent
07a0: 61 74 69 76 65 20 6f 66 20 61 20 73 63 63 0d 0a ative of a scc..
07b0: 09 09 09 2f 2f 20 74 6f 64 6f 3a 20 70 65 6e 64 ...// todo: pend
07c0: 69 6e 67 20 2d 3e 20 64 66 73 5f 6c 6f 3a 3d 49 ing -> dfs_lo:=I
07d0: 4e 54 5f 4d 41 58 0d 0a 09 09 09 73 63 63 2e 70 NT_MAX.....scc.p
07e0: 75 73 68 5f 62 61 63 6b 28 70 65 6e 64 69 6e 67 ush_back(pending
07f0: 29 2c 20 70 65 6e 64 69 6e 67 2e 63 6c 65 61 72 ), pending.clear
0800: 28 29 3b 0d 0a 0d 0a 09 09 09 2f 2f 20 63 6f 6e ();.......// con
0810: 73 74 72 75 63 74 20 73 63 63 2d 66 6f 72 65 73 struct scc-fores
0820: 74 20 28 69 66 20 6e 65 65 64 65 64 29 0d 0a 09 t (if needed)...
0830: 09 09 73 63 63 5f 69 64 5b 76 5d 20 3d 20 73 63 ..scc_id[v] = sc
0840: 63 2e 73 69 7a 65 28 29 2d 31 3b 0d 0a 09 09 09 c.size()-1;.....
0850: 73 65 74 3c 69 6e 74 3e 20 63 68 69 6c 64 72 65 set<int> childre
0860: 6e 3b 0d 0a 09 09 09 66 6f 72 28 69 6e 74 20 69 n;.....for(int i
0870: 3d 30 3b 20 69 3c 47 5b 76 5d 2e 73 69 7a 65 28 =0; i<G[v].size(
0880: 29 3b 20 2b 2b 69 29 0d 0a 09 09 09 09 69 66 28 ); ++i)......if(
0890: 20 64 66 73 5f 6c 6f 5b 47 5b 76 5d 5b 69 5d 5d dfs_lo[G[v][i]]
08a0: 20 21 3d 20 76 20 29 0d 0a 09 09 09 09 09 63 68 != v ).......ch
08b0: 69 6c 64 72 65 6e 2e 69 6e 73 65 72 74 28 20 73 ildren.insert( s
08c0: 63 63 5f 69 64 5b 64 66 73 5f 6c 6f 5b 47 5b 76 cc_id[dfs_lo[G[v
08d0: 5d 5b 69 5d 5d 5d 20 29 3b 0d 0a 09 09 09 66 6f ][i]]] );.....fo
08e0: 72 65 73 74 2e 70 75 73 68 5f 62 61 63 6b 28 20 rest.push_back(
08f0: 76 65 63 74 6f 72 3c 69 6e 74 3e 28 63 68 69 6c vector<int>(chil
0900: 64 72 65 6e 2e 62 65 67 69 6e 28 29 2c 20 63 68 dren.begin(), ch
0910: 69 6c 64 72 65 6e 2e 65 6e 64 28 29 29 20 29 3b ildren.end()) );
0920: 0d 0a 09 09 7d 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d ....}...}..};...
0930: 0a 0d 0a 63 6c 61 73 73 20 49 6d 70 6f 73 73 69 ...class Impossi
0940: 62 6c 65 47 61 6d 65 20 7b 20 70 75 62 6c 69 63 bleGame { public
0950: 3a 0d 0a 09 73 74 61 74 69 63 20 4c 4c 20 43 28 :...static LL C(
0960: 4c 4c 20 6e 2c 20 4c 4c 20 6b 29 20 7b 0d 0a 09 LL n, LL k) {...
0970: 09 4c 4c 20 76 20 3d 20 31 3b 0d 0a 09 09 66 6f .LL v = 1;....fo
0980: 72 28 69 6e 74 20 69 3d 31 3b 20 69 3c 3d 6b 3b r(int i=1; i<=k;
0990: 20 2b 2b 69 29 0d 0a 09 09 09 76 20 3d 20 76 20 ++i).....v = v
09a0: 2a 20 28 6e 2b 31 2d 69 29 20 2f 20 69 3b 0d 0a * (n+1-i) / i;..
09b0: 09 09 72 65 74 75 72 6e 20 76 3b 0d 0a 09 7d 0d ..return v;...}.
09c0: 0a 09 73 74 61 74 69 63 20 4c 4c 20 77 65 69 67 ..static LL weig
09d0: 68 74 28 4c 4c 20 61 2c 20 4c 4c 20 62 2c 20 4c ht(LL a, LL b, L
09e0: 4c 20 63 2c 20 4c 4c 20 64 29 20 7b 0d 0a 09 09 L c, LL d) {....
09f0: 72 65 74 75 72 6e 20 43 28 61 2b 62 2b 63 2b 64 return C(a+b+c+d
0a00: 2c 61 29 20 2a 20 43 28 62 2b 63 2b 64 2c 62 29 ,a) * C(b+c+d,b)
0a10: 20 2a 20 43 28 63 2b 64 2c 63 29 3b 0d 0a 09 7d * C(c+d,c);...}
0a20: 0d 0a 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 67 .....long long g
0a30: 65 74 4d 69 6e 69 6d 75 6d 28 69 6e 74 20 6b 2c etMinimum(int k,
0a40: 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e vector <string>
0a50: 20 62 65 66 6f 72 65 2c 20 76 65 63 74 6f 72 20 before, vector
0a60: 3c 73 74 72 69 6e 67 3e 20 61 66 74 65 72 29 20 <string> after)
0a70: 0d 0a 09 7b 0d 0a 09 09 76 65 63 74 6f 72 3c 20 ...{....vector<
0a80: 70 61 69 72 3c 20 76 65 63 74 6f 72 3c 69 6e 74 pair< vector<int
0a90: 3e 2c 20 76 65 63 74 6f 72 3c 69 6e 74 3e 20 3e >, vector<int> >
0aa0: 20 3e 20 64 69 66 3b 0d 0a 09 09 66 6f 72 28 69 > dif;....for(i
0ab0: 6e 74 20 69 3d 30 3b 20 69 3c 61 66 74 65 72 2e nt i=0; i<after.
0ac0: 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0d 0a 09 09 size(); ++i)....
0ad0: 7b 0d 0a 09 09 09 76 65 63 74 6f 72 3c 69 6e 74 {.....vector<int
0ae0: 3e 20 62 65 28 34 29 2c 20 61 66 28 34 29 3b 0d > be(4), af(4);.
0af0: 0a 09 09 09 66 6f 72 28 69 6e 74 20 6a 3d 30 3b ....for(int j=0;
0b00: 20 6a 3c 62 65 66 6f 72 65 5b 69 5d 2e 73 69 7a j<before[i].siz
0b10: 65 28 29 3b 20 2b 2b 6a 29 20 62 65 5b 62 65 66 e(); ++j) be[bef
0b20: 6f 72 65 5b 69 5d 5b 6a 5d 2d 27 41 27 5d 20 2b ore[i][j]-'A'] +
0b30: 2b 3b 0d 0a 09 09 09 66 6f 72 28 69 6e 74 20 6a +;.....for(int j
0b40: 3d 30 3b 20 6a 3c 20 61 66 74 65 72 5b 69 5d 2e =0; j< after[i].
0b50: 73 69 7a 65 28 29 3b 20 2b 2b 6a 29 20 61 66 5b size(); ++j) af[
0b60: 20 61 66 74 65 72 5b 69 5d 5b 6a 5d 2d 27 41 27 after[i][j]-'A'
0b70: 5d 20 2b 2b 3b 0d 0a 09 09 09 64 69 66 2e 70 75 ] ++;.....dif.pu
0b80: 73 68 5f 62 61 63 6b 28 20 6d 61 6b 65 5f 70 61 sh_back( make_pa
0b90: 69 72 28 62 65 2c 61 66 29 20 29 3b 0d 0a 09 09 ir(be,af) );....
0ba0: 7d 0d 0a 0d 0a 09 09 47 72 61 70 68 3c 20 76 65 }......Graph< ve
0bb0: 63 74 6f 72 3c 69 6e 74 3e 20 3e 20 47 3b 0d 0a ctor<int> > G;..
0bc0: 0d 0a 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 ....vector<int>
0bd0: 76 28 34 29 3b 0d 0a 09 09 66 6f 72 28 76 5b 30 v(4);....for(v[0
0be0: 5d 3d 30 3b 20 76 5b 30 5d 3c 3d 6b 3b 20 2b 2b ]=0; v[0]<=k; ++
0bf0: 76 5b 30 5d 29 0d 0a 09 09 66 6f 72 28 76 5b 31 v[0])....for(v[1
0c00: 5d 3d 30 3b 20 76 5b 30 5d 2b 76 5b 31 5d 3c 3d ]=0; v[0]+v[1]<=
0c10: 6b 3b 20 2b 2b 76 5b 31 5d 29 0d 0a 09 09 66 6f k; ++v[1])....fo
0c20: 72 28 76 5b 32 5d 3d 30 3b 20 76 5b 30 5d 2b 76 r(v[2]=0; v[0]+v
0c30: 5b 31 5d 2b 76 5b 32 5d 3c 3d 6b 3b 20 2b 2b 76 [1]+v[2]<=k; ++v
0c40: 5b 32 5d 29 0d 0a 09 09 66 6f 72 28 76 5b 33 5d [2])....for(v[3]
0c50: 3d 30 3b 20 76 5b 30 5d 2b 76 5b 31 5d 2b 76 5b =0; v[0]+v[1]+v[
0c60: 32 5d 2b 76 5b 33 5d 3c 3d 6b 3b 20 2b 2b 76 5b 2]+v[3]<=k; ++v[
0c70: 33 5d 29 0d 0a 09 09 7b 0d 0a 09 09 09 47 2e 76 3])....{.....G.v
0c80: 65 72 74 28 76 29 3b 0d 0a 09 09 09 66 6f 72 28 ert(v);.....for(
0c90: 69 6e 74 20 69 3d 30 3b 20 69 3c 64 69 66 2e 73 int i=0; i<dif.s
0ca0: 69 7a 65 28 29 3b 20 2b 2b 69 29 0d 0a 09 09 09 ize(); ++i).....
0cb0: 7b 0d 0a 09 09 09 09 62 6f 6f 6c 20 64 61 6d 65 {......bool dame
0cc0: 20 3d 20 66 61 6c 73 65 3b 0d 0a 0d 0a 09 09 09 = false;.......
0cd0: 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 75 20 3d .vector<int> u =
0ce0: 20 76 3b 0d 0a 09 09 09 09 66 6f 72 28 69 6e 74 v;......for(int
0cf0: 20 6b 3d 30 3b 20 6b 3c 34 3b 20 2b 2b 6b 29 0d k=0; k<4; ++k).
0d00: 0a 09 09 09 09 7b 0d 0a 09 09 09 09 09 69 66 28 .....{.......if(
0d10: 20 28 75 5b 6b 5d 2d 3d 64 69 66 5b 69 5d 2e 66 (u[k]-=dif[i].f
0d20: 69 72 73 74 5b 6b 5d 29 20 3c 20 30 20 29 0d 0a irst[k]) < 0 )..
0d30: 09 09 09 09 09 09 64 61 6d 65 20 3d 20 74 72 75 ......dame = tru
0d40: 65 3b 0d 0a 09 09 09 09 09 75 5b 6b 5d 20 2b 3d e;.......u[k] +=
0d50: 20 64 69 66 5b 69 5d 2e 73 65 63 6f 6e 64 5b 6b dif[i].second[k
0d60: 5d 3b 0d 0a 09 09 09 09 7d 0d 0a 09 09 09 09 69 ];......}......i
0d70: 66 28 20 21 64 61 6d 65 20 29 0d 0a 09 09 09 09 f( !dame )......
0d80: 09 47 2e 65 64 67 65 28 76 2c 20 75 29 3b 0d 0a .G.edge(v, u);..
0d90: 09 09 09 7d 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 53 ...}....}......S
0da0: 74 72 6f 6e 67 6c 79 43 6f 6e 6e 65 63 74 65 64 tronglyConnected
0db0: 43 6f 6d 70 6f 6e 65 6e 74 20 73 63 63 28 47 2e Component scc(G.
0dc0: 47 29 3b 0d 0a 09 09 72 65 74 75 72 6e 20 30 3b G);....return 0;
0dd0: 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f 2f 20 42 ...}..};....// B
0de0: 45 47 49 4e 20 43 55 54 20 48 45 52 45 0d 0a 23 EGIN CUT HERE..#
0df0: 69 6e 63 6c 75 64 65 20 3c 63 74 69 6d 65 3e 0d include <ctime>.
0e00: 0a 64 6f 75 62 6c 65 20 73 74 61 72 74 5f 74 69 .double start_ti
0e10: 6d 65 3b 20 73 74 72 69 6e 67 20 74 69 6d 65 72 me; string timer
0e20: 28 29 0d 0a 20 7b 20 6f 73 74 72 69 6e 67 73 74 ().. { ostringst
0e30: 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c 3c 20 22 ream os; os << "
0e40: 20 28 22 20 3c 3c 20 69 6e 74 28 28 63 6c 6f 63 (" << int((cloc
0e50: 6b 28 29 2d 73 74 61 72 74 5f 74 69 6d 65 29 2f k()-start_time)/
0e60: 43 4c 4f 43 4b 53 5f 50 45 52 5f 53 45 43 2a 31 CLOCKS_PER_SEC*1
0e70: 30 30 30 29 20 3c 3c 20 22 20 6d 73 65 63 29 22 000) << " msec)"
0e80: 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 74 72 28 ; return os.str(
0e90: 29 3b 20 7d 0d 0a 74 65 6d 70 6c 61 74 65 3c 74 ); }..template<t
0ea0: 79 70 65 6e 61 6d 65 20 54 3e 20 6f 73 74 72 65 ypename T> ostre
0eb0: 61 6d 26 20 6f 70 65 72 61 74 6f 72 3c 3c 28 6f am& operator<<(o
0ec0: 73 74 72 65 61 6d 26 20 6f 73 2c 20 63 6f 6e 73 stream& os, cons
0ed0: 74 20 76 65 63 74 6f 72 3c 54 3e 26 20 76 29 0d t vector<T>& v).
0ee0: 0a 20 7b 20 6f 73 20 3c 3c 20 22 7b 20 22 3b 0d . { os << "{ ";.
0ef0: 0a 20 20 20 66 6f 72 28 74 79 70 65 6e 61 6d 65 . for(typename
0f00: 20 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 6f 6e 73 vector<T>::cons
0f10: 74 5f 69 74 65 72 61 74 6f 72 20 69 74 3d 76 2e t_iterator it=v.
0f20: 62 65 67 69 6e 28 29 3b 20 69 74 21 3d 76 2e 65 begin(); it!=v.e
0f30: 6e 64 28 29 3b 20 2b 2b 69 74 29 0d 0a 20 20 20 nd(); ++it)..
0f40: 6f 73 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 2a 69 os << '\"' << *i
0f50: 74 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 28 69 74 t << '\"' << (it
0f60: 2b 31 3d 3d 76 2e 65 6e 64 28 29 20 3f 20 22 22 +1==v.end() ? ""
0f70: 20 3a 20 22 2c 20 22 29 3b 20 6f 73 20 3c 3c 20 : ", "); os <<
0f80: 22 20 7d 22 3b 20 72 65 74 75 72 6e 20 6f 73 3b " }"; return os;
0f90: 20 7d 0d 0a 76 6f 69 64 20 76 65 72 69 66 79 5f }..void verify_
0fa0: 63 61 73 65 28 63 6f 6e 73 74 20 6c 6f 6e 67 20 case(const long
0fb0: 6c 6f 6e 67 26 20 45 78 70 65 63 74 65 64 2c 20 long& Expected,
0fc0: 63 6f 6e 73 74 20 6c 6f 6e 67 20 6c 6f 6e 67 26 const long long&
0fd0: 20 52 65 63 65 69 76 65 64 29 20 7b 0d 0a 20 62 Received) {.. b
0fe0: 6f 6f 6c 20 6f 6b 20 3d 20 28 45 78 70 65 63 74 ool ok = (Expect
0ff0: 65 64 20 3d 3d 20 52 65 63 65 69 76 65 64 29 3b ed == Received);
1000: 0d 0a 20 69 66 28 6f 6b 29 20 63 65 72 72 20 3c .. if(ok) cerr <
1010: 3c 20 22 50 41 53 53 45 44 22 20 3c 3c 20 74 69 < "PASSED" << ti
1020: 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 20 20 mer() << endl;
1030: 65 6c 73 65 20 7b 20 63 65 72 72 20 3c 3c 20 22 else { cerr << "
1040: 46 41 49 4c 45 44 22 20 3c 3c 20 74 69 6d 65 72 FAILED" << timer
1050: 28 29 20 3c 3c 20 65 6e 64 6c 3b 0d 0a 20 63 65 () << endl;.. ce
1060: 72 72 20 3c 3c 20 22 5c 74 6f 3a 20 5c 22 22 20 rr << "\to: \""
1070: 3c 3c 20 45 78 70 65 63 74 65 64 20 3c 3c 20 27 << Expected << '
1080: 5c 22 27 20 3c 3c 20 65 6e 64 6c 20 3c 3c 20 22 \"' << endl << "
1090: 5c 74 78 3a 20 5c 22 22 20 3c 3c 20 52 65 63 65 \tx: \"" << Rece
10a0: 69 76 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 ived << '\"' <<
10b0: 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 23 64 65 66 69 endl; } }..#defi
10c0: 6e 65 20 43 41 53 45 28 4e 29 20 7b 63 65 72 72 ne CASE(N) {cerr
10d0: 20 3c 3c 20 22 54 65 73 74 20 43 61 73 65 20 23 << "Test Case #
10e0: 22 20 3c 3c 20 4e 20 3c 3c 20 22 2e 2e 2e 22 20 " << N << "..."
10f0: 3c 3c 20 66 6c 75 73 68 3b 20 73 74 61 72 74 5f << flush; start_
1100: 74 69 6d 65 3d 63 6c 6f 63 6b 28 29 3b 0d 0a 23 time=clock();..#
1110: 64 65 66 69 6e 65 20 45 4e 44 09 20 76 65 72 69 define END. veri
1120: 66 79 5f 63 61 73 65 28 5f 2c 20 49 6d 70 6f 73 fy_case(_, Impos
1130: 73 69 62 6c 65 47 61 6d 65 28 29 2e 67 65 74 4d sibleGame().getM
1140: 69 6e 69 6d 75 6d 28 6b 2c 20 62 65 66 6f 72 65 inimum(k, before
1150: 2c 20 61 66 74 65 72 29 29 3b 7d 0d 0a 69 6e 74 , after));}..int
1160: 20 6d 61 69 6e 28 29 7b 0d 0a 0d 0a 43 41 53 45 main(){....CASE
1170: 28 30 29 0d 0a 09 69 6e 74 20 6b 20 3d 20 31 3b (0)...int k = 1;
1180: 20 0d 0a 09 73 74 72 69 6e 67 20 62 65 66 6f 72 ...string befor
1190: 65 5f 5b 5d 20 3d 20 7b 20 22 41 22 20 7d 0d 0a e_[] = { "A" }..
11a0: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 ;... vector <st
11b0: 72 69 6e 67 3e 20 62 65 66 6f 72 65 28 62 65 66 ring> before(bef
11c0: 6f 72 65 5f 2c 20 62 65 66 6f 72 65 5f 2b 73 69 ore_, before_+si
11d0: 7a 65 6f 66 28 62 65 66 6f 72 65 5f 29 2f 73 69 zeof(before_)/si
11e0: 7a 65 6f 66 28 2a 62 65 66 6f 72 65 5f 29 29 3b zeof(*before_));
11f0: 20 0d 0a 09 73 74 72 69 6e 67 20 61 66 74 65 72 ...string after
1200: 5f 5b 5d 20 3d 20 7b 20 22 42 22 20 7d 0d 0a 3b _[] = { "B" }..;
1210: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 ... vector <str
1220: 69 6e 67 3e 20 61 66 74 65 72 28 61 66 74 65 72 ing> after(after
1230: 5f 2c 20 61 66 74 65 72 5f 2b 73 69 7a 65 6f 66 _, after_+sizeof
1240: 28 61 66 74 65 72 5f 29 2f 73 69 7a 65 6f 66 28 (after_)/sizeof(
1250: 2a 61 66 74 65 72 5f 29 29 3b 20 0d 0a 09 6c 6f *after_)); ...lo
1260: 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 32 4c 4c 3b ng long _ = 2LL;
1270: 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 31 29 0d ..END..CASE(1).
1280: 0a 09 69 6e 74 20 6b 20 3d 20 32 3b 20 0d 0a 09 ..int k = 2; ...
1290: 73 74 72 69 6e 67 20 62 65 66 6f 72 65 5f 5b 5d string before_[]
12a0: 20 3d 20 7b 20 22 41 22 2c 20 22 41 22 2c 20 22 = { "A", "A", "
12b0: 44 22 20 7d 0d 0a 3b 0d 0a 09 20 20 76 65 63 74 D" }..;... vect
12c0: 6f 72 20 3c 73 74 72 69 6e 67 3e 20 62 65 66 6f or <string> befo
12d0: 72 65 28 62 65 66 6f 72 65 5f 2c 20 62 65 66 6f re(before_, befo
12e0: 72 65 5f 2b 73 69 7a 65 6f 66 28 62 65 66 6f 72 re_+sizeof(befor
12f0: 65 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 65 66 6f e_)/sizeof(*befo
1300: 72 65 5f 29 29 3b 20 0d 0a 09 73 74 72 69 6e 67 re_)); ...string
1310: 20 61 66 74 65 72 5f 5b 5d 20 3d 20 7b 20 22 42 after_[] = { "B
1320: 22 2c 20 22 43 22 2c 20 22 44 22 20 7d 0d 0a 3b ", "C", "D" }..;
1330: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 ... vector <str
1340: 69 6e 67 3e 20 61 66 74 65 72 28 61 66 74 65 72 ing> after(after
1350: 5f 2c 20 61 66 74 65 72 5f 2b 73 69 7a 65 6f 66 _, after_+sizeof
1360: 28 61 66 74 65 72 5f 29 2f 73 69 7a 65 6f 66 28 (after_)/sizeof(
1370: 2a 61 66 74 65 72 5f 29 29 3b 20 0d 0a 09 6c 6f *after_)); ...lo
1380: 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 35 4c 4c 3b ng long _ = 5LL;
1390: 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 32 29 0d ..END..CASE(2).
13a0: 0a 09 69 6e 74 20 6b 20 3d 20 32 3b 20 0d 0a 09 ..int k = 2; ...
13b0: 73 74 72 69 6e 67 20 62 65 66 6f 72 65 5f 5b 5d string before_[]
13c0: 20 3d 20 7b 20 22 42 22 2c 20 22 43 22 2c 20 22 = { "B", "C", "
13d0: 44 22 20 7d 0d 0a 3b 0d 0a 09 20 20 76 65 63 74 D" }..;... vect
13e0: 6f 72 20 3c 73 74 72 69 6e 67 3e 20 62 65 66 6f or <string> befo
13f0: 72 65 28 62 65 66 6f 72 65 5f 2c 20 62 65 66 6f re(before_, befo
1400: 72 65 5f 2b 73 69 7a 65 6f 66 28 62 65 66 6f 72 re_+sizeof(befor
1410: 65 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 65 66 6f e_)/sizeof(*befo
1420: 72 65 5f 29 29 3b 20 0d 0a 09 73 74 72 69 6e 67 re_)); ...string
1430: 20 61 66 74 65 72 5f 5b 5d 20 3d 20 7b 20 22 43 after_[] = { "C
1440: 22 2c 20 22 44 22 2c 20 22 42 22 20 7d 0d 0a 3b ", "D", "B" }..;
1450: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 ... vector <str
1460: 69 6e 67 3e 20 61 66 74 65 72 28 61 66 74 65 72 ing> after(after
1470: 5f 2c 20 61 66 74 65 72 5f 2b 73 69 7a 65 6f 66 _, after_+sizeof
1480: 28 61 66 74 65 72 5f 29 2f 73 69 7a 65 6f 66 28 (after_)/sizeof(
1490: 2a 61 66 74 65 72 5f 29 29 3b 20 0d 0a 09 6c 6f *after_)); ...lo
14a0: 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 39 4c 4c 3b ng long _ = 9LL;
14b0: 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 33 29 0d ..END..CASE(3).
14c0: 0a 09 69 6e 74 20 6b 20 3d 20 36 3b 20 0d 0a 09 ..int k = 6; ...
14d0: 73 74 72 69 6e 67 20 62 65 66 6f 72 65 5f 5b 5d string before_[]
14e0: 20 3d 20 7b 20 22 41 41 42 42 43 22 2c 20 22 41 = { "AABBC", "A
14f0: 41 41 41 44 41 22 2c 20 22 41 41 41 43 41 22 2c AAADA", "AAACA",
1500: 20 22 43 41 42 41 41 22 2c 20 22 41 41 41 41 41 "CABAA", "AAAAA
1510: 41 22 2c 20 22 42 41 41 41 41 22 20 7d 0d 0a 3b A", "BAAAA" }..;
1520: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 ... vector <str
1530: 69 6e 67 3e 20 62 65 66 6f 72 65 28 62 65 66 6f ing> before(befo
1540: 72 65 5f 2c 20 62 65 66 6f 72 65 5f 2b 73 69 7a re_, before_+siz
1550: 65 6f 66 28 62 65 66 6f 72 65 5f 29 2f 73 69 7a eof(before_)/siz
1560: 65 6f 66 28 2a 62 65 66 6f 72 65 5f 29 29 3b 20 eof(*before_));
1570: 0d 0a 09 73 74 72 69 6e 67 20 61 66 74 65 72 5f ...string after_
1580: 5b 5d 20 3d 20 7b 20 22 41 41 43 43 42 22 2c 20 [] = { "AACCB",
1590: 22 44 41 41 41 42 43 22 2c 20 22 41 41 41 41 44 "DAAABC", "AAAAD
15a0: 22 2c 20 22 41 42 43 42 41 22 2c 20 22 41 41 42 ", "ABCBA", "AAB
15b0: 41 41 41 22 2c 20 22 41 41 43 41 41 22 20 7d 0d AAA", "AACAA" }.
15c0: 0a 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 .;... vector <s
15d0: 74 72 69 6e 67 3e 20 61 66 74 65 72 28 61 66 74 tring> after(aft
15e0: 65 72 5f 2c 20 61 66 74 65 72 5f 2b 73 69 7a 65 er_, after_+size
15f0: 6f 66 28 61 66 74 65 72 5f 29 2f 73 69 7a 65 6f of(after_)/sizeo
1600: 66 28 2a 61 66 74 65 72 5f 29 29 3b 20 0d 0a 09 f(*after_)); ...
1610: 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 34 39 long long _ = 49
1620: 39 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 2f 2a 0d 0a 9LL; ..END../*..
1630: 43 41 53 45 28 34 29 0d 0a 09 69 6e 74 20 6b 20 CASE(4)...int k
1640: 3d 20 3b 20 0d 0a 09 73 74 72 69 6e 67 20 62 65 = ; ...string be
1650: 66 6f 72 65 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 fore_[] = ;...
1660: 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 vector <string>
1670: 62 65 66 6f 72 65 28 62 65 66 6f 72 65 5f 2c 20 before(before_,
1680: 62 65 66 6f 72 65 5f 2b 73 69 7a 65 6f 66 28 62 before_+sizeof(b
1690: 65 66 6f 72 65 5f 29 2f 73 69 7a 65 6f 66 28 2a efore_)/sizeof(*
16a0: 62 65 66 6f 72 65 5f 29 29 3b 20 0d 0a 09 73 74 before_)); ...st
16b0: 72 69 6e 67 20 61 66 74 65 72 5f 5b 5d 20 3d 20 ring after_[] =
16c0: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 ;... vector <st
16d0: 72 69 6e 67 3e 20 61 66 74 65 72 28 61 66 74 65 ring> after(afte
16e0: 72 5f 2c 20 61 66 74 65 72 5f 2b 73 69 7a 65 6f r_, after_+sizeo
16f0: 66 28 61 66 74 65 72 5f 29 2f 73 69 7a 65 6f 66 f(after_)/sizeof
1700: 28 2a 61 66 74 65 72 5f 29 29 3b 20 0d 0a 09 6c (*after_)); ...l
1710: 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 4c 4c 3b ong long _ = LL;
1720: 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 35 29 0d ..END..CASE(5).
1730: 0a 09 69 6e 74 20 6b 20 3d 20 3b 20 0d 0a 09 73 ..int k = ; ...s
1740: 74 72 69 6e 67 20 62 65 66 6f 72 65 5f 5b 5d 20 tring before_[]
1750: 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c = ;... vector <
1760: 73 74 72 69 6e 67 3e 20 62 65 66 6f 72 65 28 62 string> before(b
1770: 65 66 6f 72 65 5f 2c 20 62 65 66 6f 72 65 5f 2b efore_, before_+
1780: 73 69 7a 65 6f 66 28 62 65 66 6f 72 65 5f 29 2f sizeof(before_)/
1790: 73 69 7a 65 6f 66 28 2a 62 65 66 6f 72 65 5f 29 sizeof(*before_)
17a0: 29 3b 20 0d 0a 09 73 74 72 69 6e 67 20 61 66 74 ); ...string aft
17b0: 65 72 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 er_[] = ;... ve
17c0: 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 61 66 ctor <string> af
17d0: 74 65 72 28 61 66 74 65 72 5f 2c 20 61 66 74 65 ter(after_, afte
17e0: 72 5f 2b 73 69 7a 65 6f 66 28 61 66 74 65 72 5f r_+sizeof(after_
17f0: 29 2f 73 69 7a 65 6f 66 28 2a 61 66 74 65 72 5f )/sizeof(*after_
1800: 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 )); ...long long
1810: 20 5f 20 3d 20 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a _ = LL; ..END..
1820: 2a 2f 0d 0a 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 */..}..// END CU
1830: 54 20 48 45 52 45 0d 0a T HERE..