Artifact 7827709f822d3c66beb5c1f97e2894b2439e9dd4:
0000: 2f 2f 20 54 4f 44 4f 20 3a 20 6f 70 74 69 6d 69 // TODO : optimi
0010: 7a 65 20 74 6f 20 4f 28 6e 20 6c 6f 67 20 6e 29 ze to O(n log n)
0020: 0a 2f 2f 20 20 63 75 72 72 65 6e 74 20 76 65 72 .// current ver
0030: 73 69 6f 6e 20 6c 6f 6f 6b 73 20 74 6f 20 62 65 sion looks to be
0040: 20 72 75 6e 6e 69 6e 67 20 69 6e 20 4f 28 6e 5e running in O(n^
0050: 32 29 20 2e 2e 2e 20 6f 72 7a 0a 2f 2f 0a 2f 2f 2) ... orz.//.//
0060: 20 54 4f 44 4f 20 3a 20 63 6c 65 61 6e 20 75 70 TODO : clean up
0070: 20 61 73 20 61 20 6c 69 62 72 61 72 79 0a 2f 2f as a library.//
0080: 0a 2f 2f 20 43 6f 70 79 26 50 61 73 74 65 20 66 .// Copy&Paste f
0090: 72 6f 6d 20 53 52 4d 35 36 32 20 44 69 76 31 20 rom SRM562 Div1
00a0: 48 61 72 64 0a 0a 09 2f 2f 20 49 6e 70 75 74 20 Hard...// Input
00b0: 69 73 20 67 69 76 65 6e 20 61 73 3a 0a 09 2f 2f is given as:..//
00c0: 20 20 20 20 76 2d 2d 2d 2d 63 2d 2d 2d 2d 3e 47 v----c---->G
00d0: 5b 76 5d 5b 63 5d 0a 09 2f 2f 20 4d 75 73 74 20 [v][c]..// Must
00e0: 62 65 20 61 20 63 6f 6d 70 6c 65 74 65 20 61 75 be a complete au
00f0: 74 6f 6d 61 74 6f 6e 2e 0a 09 2f 2f 20 21 21 21 tomaton...// !!!
0100: 20 54 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 63 The following c
0110: 6f 64 65 20 69 73 20 61 73 73 75 6d 69 6e 67 20 ode is assuming
0120: 7c 63 7c 3d 3d 34 20 21 21 21 0a 09 2f 2f 0a 09 |c|==4 !!!..//..
0130: 2f 2f 20 21 21 21 20 54 68 65 20 66 6f 6c 6c 6f // !!! The follo
0140: 77 69 6e 67 20 63 6f 64 65 20 69 73 20 61 73 73 wing code is ass
0150: 75 6d 69 6e 67 20 74 68 65 20 66 69 6e 61 6c 20 uming the final
0160: 73 74 61 74 65 20 69 73 20 7b 30 7d 2e 0a 09 2f state is {0}.../
0170: 2f 0a 09 6d 69 6e 74 20 73 6f 6c 76 65 28 76 65 /..mint solve(ve
0180: 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 69 6e 74 ctor< vector<int
0190: 3e 20 3e 26 20 47 29 0a 09 7b 0a 09 09 76 65 63 > >& G)..{...vec
01a0: 74 6f 72 3c 20 76 65 63 74 6f 72 3c 69 6e 74 3e tor< vector<int>
01b0: 20 3e 20 73 65 74 5f 62 75 66 66 65 72 3b 0a 09 > set_buffer;..
01c0: 09 73 65 74 3c 69 6e 74 3e 20 61 63 74 69 76 65 .set<int> active
01d0: 5f 73 65 74 73 3b 0a 09 09 73 65 74 3c 69 6e 74 _sets;...set<int
01e0: 3e 20 61 63 74 69 76 65 5f 73 70 6c 69 74 74 65 > active_splitte
01f0: 72 73 3b 0a 0a 09 09 7b 0a 09 09 09 73 65 74 5f rs;....{....set_
0200: 62 75 66 66 65 72 2e 70 75 73 68 5f 62 61 63 6b buffer.push_back
0210: 28 20 76 65 63 74 6f 72 3c 69 6e 74 3e 28 31 2c ( vector<int>(1,
0220: 30 29 20 29 3b 0a 09 09 09 76 65 63 74 6f 72 3c 0) );....vector<
0230: 69 6e 74 3e 20 61 6c 6c 3b 0a 09 09 09 66 6f 72 int> all;....for
0240: 28 69 6e 74 20 76 3d 31 3b 20 76 3c 47 2e 73 69 (int v=1; v<G.si
0250: 7a 65 28 29 3b 20 2b 2b 76 29 0a 09 09 09 09 61 ze(); ++v).....a
0260: 6c 6c 2e 70 75 73 68 5f 62 61 63 6b 28 76 29 3b ll.push_back(v);
0270: 0a 09 09 09 73 65 74 5f 62 75 66 66 65 72 2e 70 ....set_buffer.p
0280: 75 73 68 5f 62 61 63 6b 28 61 6c 6c 29 3b 0a 0a ush_back(all);..
0290: 09 09 09 61 63 74 69 76 65 5f 73 65 74 73 2e 69 ...active_sets.i
02a0: 6e 73 65 72 74 28 30 29 3b 0a 09 09 09 61 63 74 nsert(0);....act
02b0: 69 76 65 5f 73 65 74 73 2e 69 6e 73 65 72 74 28 ive_sets.insert(
02c0: 31 29 3b 0a 09 09 09 61 63 74 69 76 65 5f 73 70 1);....active_sp
02d0: 6c 69 74 74 65 72 73 2e 69 6e 73 65 72 74 28 30 litters.insert(0
02e0: 29 3b 0a 09 09 7d 0a 0a 09 09 77 68 69 6c 65 28 );...}....while(
02f0: 21 61 63 74 69 76 65 5f 73 70 6c 69 74 74 65 72 !active_splitter
0300: 73 2e 65 6d 70 74 79 28 29 29 0a 09 09 7b 0a 09 s.empty())...{..
0310: 09 09 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 69 ..const vector<i
0320: 6e 74 3e 26 20 73 70 6c 76 20 3d 20 73 65 74 5f nt>& splv = set_
0330: 62 75 66 66 65 72 5b 2a 61 63 74 69 76 65 5f 73 buffer[*active_s
0340: 70 6c 69 74 74 65 72 73 2e 62 65 67 69 6e 28 29 plitters.begin()
0350: 5d 3b 0a 09 09 09 73 65 74 3c 69 6e 74 3e 20 73 ];....set<int> s
0360: 70 6c 28 73 70 6c 76 2e 62 65 67 69 6e 28 29 2c pl(splv.begin(),
0370: 20 73 70 6c 76 2e 65 6e 64 28 29 29 3b 0a 09 09 splv.end());...
0380: 09 61 63 74 69 76 65 5f 73 70 6c 69 74 74 65 72 .active_splitter
0390: 73 2e 65 72 61 73 65 28 61 63 74 69 76 65 5f 73 s.erase(active_s
03a0: 70 6c 69 74 74 65 72 73 2e 62 65 67 69 6e 28 29 plitters.begin()
03b0: 29 3b 0a 0a 09 09 09 66 6f 72 28 69 6e 74 20 64 );.....for(int d
03c0: 3d 30 3b 20 64 3c 34 3b 20 2b 2b 64 29 0a 09 09 =0; d<4; ++d)...
03d0: 09 66 6f 72 28 73 65 74 3c 69 6e 74 3e 3a 3a 69 .for(set<int>::i
03e0: 74 65 72 61 74 6f 72 20 69 74 3d 61 63 74 69 76 terator it=activ
03f0: 65 5f 73 65 74 73 2e 62 65 67 69 6e 28 29 3b 20 e_sets.begin();
0400: 69 74 21 3d 61 63 74 69 76 65 5f 73 65 74 73 2e it!=active_sets.
0410: 65 6e 64 28 29 3b 20 29 0a 09 09 09 7b 0a 09 09 end(); )....{...
0420: 09 09 69 6e 74 20 69 69 20 3d 20 2a 69 74 2b 2b ..int ii = *it++
0430: 3b 0a 09 09 09 09 63 6f 6e 73 74 20 76 65 63 74 ;.....const vect
0440: 6f 72 3c 69 6e 74 3e 26 20 63 75 72 20 3d 20 73 or<int>& cur = s
0450: 65 74 5f 62 75 66 66 65 72 5b 69 69 5d 3b 0a 09 et_buffer[ii];..
0460: 09 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 74 ...vector<int> t
0470: 2c 20 66 3b 0a 09 09 09 09 66 6f 72 28 69 6e 74 , f;.....for(int
0480: 20 6b 3d 30 3b 20 6b 3c 63 75 72 2e 73 69 7a 65 k=0; k<cur.size
0490: 28 29 3b 20 2b 2b 6b 29 0a 09 09 09 09 09 28 73 (); ++k)......(s
04a0: 70 6c 2e 63 6f 75 6e 74 28 47 5b 63 75 72 5b 6b pl.count(G[cur[k
04b0: 5d 5d 5b 64 5d 29 20 3f 20 74 20 3a 20 66 29 2e ]][d]) ? t : f).
04c0: 70 75 73 68 5f 62 61 63 6b 28 63 75 72 5b 6b 5d push_back(cur[k]
04d0: 29 3b 0a 09 09 09 09 69 66 28 21 74 2e 65 6d 70 );.....if(!t.emp
04e0: 74 79 28 29 20 26 26 20 21 66 2e 65 6d 70 74 79 ty() && !f.empty
04f0: 28 29 29 0a 09 09 09 09 7b 0a 09 09 09 09 09 73 ()).....{......s
0500: 65 74 5f 62 75 66 66 65 72 2e 70 75 73 68 5f 62 et_buffer.push_b
0510: 61 63 6b 28 74 29 3b 0a 09 09 09 09 09 73 65 74 ack(t);......set
0520: 5f 62 75 66 66 65 72 2e 70 75 73 68 5f 62 61 63 _buffer.push_bac
0530: 6b 28 66 29 3b 0a 09 09 09 09 09 61 63 74 69 76 k(f);......activ
0540: 65 5f 73 65 74 73 2e 69 6e 73 65 72 74 28 73 65 e_sets.insert(se
0550: 74 5f 62 75 66 66 65 72 2e 73 69 7a 65 28 29 2d t_buffer.size()-
0560: 32 29 3b 0a 09 09 09 09 09 61 63 74 69 76 65 5f 2);......active_
0570: 73 65 74 73 2e 69 6e 73 65 72 74 28 73 65 74 5f sets.insert(set_
0580: 62 75 66 66 65 72 2e 73 69 7a 65 28 29 2d 31 29 buffer.size()-1)
0590: 3b 0a 09 09 09 09 09 69 66 28 61 63 74 69 76 65 ;......if(active
05a0: 5f 73 70 6c 69 74 74 65 72 73 2e 63 6f 75 6e 74 _splitters.count
05b0: 28 69 69 29 29 20 7b 0a 09 09 09 09 09 09 61 63 (ii)) {.......ac
05c0: 74 69 76 65 5f 73 70 6c 69 74 74 65 72 73 2e 69 tive_splitters.i
05d0: 6e 73 65 72 74 28 73 65 74 5f 62 75 66 66 65 72 nsert(set_buffer
05e0: 2e 73 69 7a 65 28 29 2d 32 29 3b 0a 09 09 09 09 .size()-2);.....
05f0: 09 09 61 63 74 69 76 65 5f 73 70 6c 69 74 74 65 ..active_splitte
0600: 72 73 2e 69 6e 73 65 72 74 28 73 65 74 5f 62 75 rs.insert(set_bu
0610: 66 66 65 72 2e 73 69 7a 65 28 29 2d 31 29 3b 0a ffer.size()-1);.
0620: 09 09 09 09 09 7d 20 65 6c 73 65 20 7b 0a 09 09 .....} else {...
0630: 09 09 09 09 61 63 74 69 76 65 5f 73 70 6c 69 74 ....active_split
0640: 74 65 72 73 2e 69 6e 73 65 72 74 28 74 2e 73 69 ters.insert(t.si
0650: 7a 65 28 29 3c 66 2e 73 69 7a 65 28 29 20 3f 20 ze()<f.size() ?
0660: 73 65 74 5f 62 75 66 66 65 72 2e 73 69 7a 65 28 set_buffer.size(
0670: 29 2d 32 20 3a 20 73 65 74 5f 62 75 66 66 65 72 )-2 : set_buffer
0680: 2e 73 69 7a 65 28 29 2d 31 29 3b 0a 09 09 09 09 .size()-1);.....
0690: 09 7d 0a 09 09 09 09 09 61 63 74 69 76 65 5f 73 .}......active_s
06a0: 70 6c 69 74 74 65 72 73 2e 65 72 61 73 65 28 69 plitters.erase(i
06b0: 69 29 3b 0a 09 09 09 09 09 61 63 74 69 76 65 5f i);......active_
06c0: 73 65 74 73 2e 65 72 61 73 65 28 69 69 29 3b 0a sets.erase(ii);.
06d0: 09 09 09 09 7d 0a 09 09 09 7d 0a 09 09 7d 0a 0a ....}....}...}..
06e0: 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 65 73 ..vector<int> es
06f0: 3b 0a 09 09 66 6f 72 28 73 65 74 3c 69 6e 74 3e ;...for(set<int>
0700: 3a 3a 69 74 65 72 61 74 6f 72 20 69 74 3d 61 63 ::iterator it=ac
0710: 74 69 76 65 5f 73 65 74 73 2e 62 65 67 69 6e 28 tive_sets.begin(
0720: 29 3b 20 69 74 21 3d 61 63 74 69 76 65 5f 73 65 ); it!=active_se
0730: 74 73 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0a ts.end(); ++it).
0740: 09 09 09 69 66 28 2a 69 74 29 0a 09 09 09 09 65 ...if(*it).....e
0750: 73 2e 70 75 73 68 5f 62 61 63 6b 28 73 65 74 5f s.push_back(set_
0760: 62 75 66 66 65 72 5b 2a 69 74 5d 2e 73 69 7a 65 buffer[*it].size
0770: 28 29 29 3b 0a 2f 2a 0a 09 09 66 6f 72 28 62 6f ());./*...for(bo
0780: 6f 6c 20 63 68 61 6e 67 65 64 3d 74 72 75 65 3b ol changed=true;
0790: 20 63 68 61 6e 67 65 64 3b 29 20 0a 09 09 7b 0a changed;) ...{.
07a0: 09 09 09 63 68 61 6e 67 65 64 3d 66 61 6c 73 65 ...changed=false
07b0: 3b 0a 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 ;....for(int i=0
07c0: 3b 20 69 3c 65 71 73 2e 73 69 7a 65 28 29 3b 20 ; i<eqs.size();
07d0: 2b 2b 69 29 20 69 66 28 21 65 71 73 5b 69 5d 2e ++i) if(!eqs[i].
07e0: 73 65 63 6f 6e 64 20 26 26 20 21 64 65 61 64 5b second && !dead[
07f0: 69 5d 29 7b 0a 09 09 09 09 73 65 74 3c 69 6e 74 i]){.....set<int
0800: 3e 20 73 70 6c 28 65 71 73 5b 69 5d 2e 66 69 72 > spl(eqs[i].fir
0810: 73 74 2e 62 65 67 69 6e 28 29 2c 20 65 71 73 5b st.begin(), eqs[
0820: 69 5d 2e 66 69 72 73 74 2e 65 6e 64 28 29 29 3b i].first.end());
0830: 0a 09 09 09 09 65 71 73 5b 69 5d 2e 73 65 63 6f .....eqs[i].seco
0840: 6e 64 20 3d 20 74 72 75 65 3b 0a 09 09 09 09 66 nd = true;.....f
0850: 6f 72 28 69 6e 74 20 6b 3d 30 3b 20 6b 3c 65 71 or(int k=0; k<eq
0860: 73 2e 73 69 7a 65 28 29 3b 20 2b 2b 6b 29 0a 09 s.size(); ++k)..
0870: 09 09 09 66 6f 72 28 69 6e 74 20 64 3d 30 3b 20 ...for(int d=0;
0880: 64 3c 34 3b 20 2b 2b 64 29 20 69 66 28 21 64 65 d<4; ++d) if(!de
0890: 61 64 5b 6b 5d 29 20 7b 0a 09 09 09 09 09 76 65 ad[k]) {......ve
08a0: 63 74 6f 72 3c 69 6e 74 3e 20 74 2c 20 66 3b 0a ctor<int> t, f;.
08b0: 09 09 09 09 09 66 6f 72 28 76 65 63 74 6f 72 3c .....for(vector<
08c0: 69 6e 74 3e 3a 3a 69 74 65 72 61 74 6f 72 20 69 int>::iterator i
08d0: 74 3d 65 71 73 5b 6b 5d 2e 66 69 72 73 74 2e 62 t=eqs[k].first.b
08e0: 65 67 69 6e 28 29 3b 20 69 74 21 3d 65 71 73 5b egin(); it!=eqs[
08f0: 6b 5d 2e 66 69 72 73 74 2e 65 6e 64 28 29 3b 20 k].first.end();
0900: 2b 2b 69 74 29 0a 09 09 09 09 09 09 28 73 70 6c ++it).......(spl
0910: 2e 63 6f 75 6e 74 28 47 5b 2a 69 74 5d 5b 64 5d .count(G[*it][d]
0920: 29 20 3f 20 74 20 3a 20 66 29 2e 70 75 73 68 5f ) ? t : f).push_
0930: 62 61 63 6b 28 2a 69 74 29 3b 0a 09 09 09 09 09 back(*it);......
0940: 69 66 28 21 74 2e 65 6d 70 74 79 28 29 20 26 26 if(!t.empty() &&
0950: 20 21 66 2e 65 6d 70 74 79 28 29 29 20 7b 0a 09 !f.empty()) {..
0960: 09 09 09 09 09 69 66 28 65 71 73 5b 6b 5d 2e 73 .....if(eqs[k].s
0970: 65 63 6f 6e 64 29 20 7b 0a 09 09 09 09 09 09 09 econd) {........
0980: 65 71 73 2e 70 75 73 68 5f 62 61 63 6b 28 6d 61 eqs.push_back(ma
0990: 6b 65 5f 70 61 69 72 28 74 2c 74 2e 73 69 7a 65 ke_pair(t,t.size
09a0: 28 29 3e 66 2e 73 69 7a 65 28 29 29 29 3b 0a 09 ()>f.size()));..
09b0: 09 09 09 09 09 09 65 71 73 2e 70 75 73 68 5f 62 ......eqs.push_b
09c0: 61 63 6b 28 6d 61 6b 65 5f 70 61 69 72 28 66 2c ack(make_pair(f,
09d0: 74 2e 73 69 7a 65 28 29 3c 3d 66 2e 73 69 7a 65 t.size()<=f.size
09e0: 28 29 29 29 3b 0a 09 09 09 09 09 09 09 64 65 61 ()));........dea
09f0: 64 2e 70 75 73 68 5f 62 61 63 6b 28 66 61 6c 73 d.push_back(fals
0a00: 65 29 3b 0a 09 09 09 09 09 09 09 64 65 61 64 2e e);........dead.
0a10: 70 75 73 68 5f 62 61 63 6b 28 66 61 6c 73 65 29 push_back(false)
0a20: 3b 0a 09 09 09 09 09 09 09 63 68 61 6e 67 65 64 ;........changed
0a30: 20 3d 20 74 72 75 65 3b 0a 09 09 09 09 09 09 7d = true;.......}
0a40: 20 65 6c 73 65 20 7b 0a 09 09 09 09 09 09 09 65 else {........e
0a50: 71 73 2e 70 75 73 68 5f 62 61 63 6b 28 6d 61 6b qs.push_back(mak
0a60: 65 5f 70 61 69 72 28 74 2c 66 61 6c 73 65 29 29 e_pair(t,false))
0a70: 3b 0a 09 09 09 09 09 09 09 65 71 73 2e 70 75 73 ;........eqs.pus
0a80: 68 5f 62 61 63 6b 28 6d 61 6b 65 5f 70 61 69 72 h_back(make_pair
0a90: 28 66 2c 66 61 6c 73 65 29 29 3b 0a 09 09 09 09 (f,false));.....
0aa0: 09 09 09 64 65 61 64 2e 70 75 73 68 5f 62 61 63 ...dead.push_bac
0ab0: 6b 28 66 61 6c 73 65 29 3b 0a 09 09 09 09 09 09 k(false);.......
0ac0: 09 64 65 61 64 2e 70 75 73 68 5f 62 61 63 6b 28 .dead.push_back(
0ad0: 66 61 6c 73 65 29 3b 0a 09 09 09 09 09 09 09 63 false);........c
0ae0: 68 61 6e 67 65 64 20 3d 20 74 72 75 65 3b 0a 09 hanged = true;..
0af0: 09 09 09 09 09 7d 0a 09 09 09 09 09 09 64 65 61 .....}.......dea
0b00: 64 5b 6b 5d 20 3d 20 74 72 75 65 3b 0a 09 09 09 d[k] = true;....
0b10: 09 09 7d 0a 09 09 09 09 7d 0a 09 09 09 7d 0a 09 ..}.....}....}..
0b20: 09 7d 0a 0a 09 09 76 65 63 74 6f 72 3c 69 6e 74 .}....vector<int
0b30: 3e 20 65 73 3b 0a 09 09 66 6f 72 28 69 6e 74 20 > es;...for(int
0b40: 69 3d 31 3b 20 69 3c 65 71 73 2e 73 69 7a 65 28 i=1; i<eqs.size(
0b50: 29 3b 20 2b 2b 69 29 20 69 66 28 21 64 65 61 64 ); ++i) if(!dead
0b60: 5b 69 5d 29 20 0a 09 09 09 65 73 2e 70 75 73 68 [i]) ....es.push
0b70: 5f 62 61 63 6b 28 65 71 73 5b 69 5d 2e 66 69 72 _back(eqs[i].fir
0b80: 73 74 2e 73 69 7a 65 28 29 29 3b 0a 2a 2f 0a 09 st.size());.*/..
0b90: 09 69 6e 74 20 73 75 6d 20 3d 20 61 63 63 75 6d .int sum = accum
0ba0: 75 6c 61 74 65 28 65 73 2e 62 65 67 69 6e 28 29 ulate(es.begin()
0bb0: 2c 20 65 73 2e 65 6e 64 28 29 2c 20 30 29 3b 0a , es.end(), 0);.
0bc0: 09 09 6d 69 6e 74 20 78 20 3d 20 50 4f 57 28 32 ..mint x = POW(2
0bd0: 2c 20 73 75 6d 29 3b 0a 09 09 66 6f 72 28 69 6e , sum);...for(in
0be0: 74 20 69 3d 30 3b 20 69 3c 65 73 2e 73 69 7a 65 t i=0; i<es.size
0bf0: 28 29 3b 20 2b 2b 69 29 0a 09 09 09 78 20 2d 3d (); ++i)....x -=
0c00: 20 50 4f 57 28 32 2c 20 65 73 5b 69 5d 29 2d 31 POW(2, es[i])-1
0c10: 3b 0a 09 09 72 65 74 75 72 6e 20 78 2d 31 3b 0a ;...return x-1;.
0c20: 09 7d 0a 0a .}..