Artifact d654c32e904bdfb1716534f66c3bc6947841cc3f:
0000: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d //--------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
0040: 2f 2f 20 42 72 75 74 65 66 6f 72 75 63 65 20 4f // Bruteforuce O
0050: 28 32 5e 56 29 20 73 65 61 72 63 68 20 77 69 74 (2^V) search wit
0060: 68 20 74 72 69 76 69 61 6c 20 65 64 61 67 61 72 h trivial edagar
0070: 69 2e 0a 2f 2f 0a 2f 2f 20 7c 56 7c 20 6d 75 73 i..//.// |V| mus
0080: 74 20 62 65 20 3c 3d 20 36 33 0a 2f 2f 0a 2f 2f t be <= 63.//.//
0090: 20 56 65 72 69 66 69 65 64 20 62 79 0a 2f 2f 20 Verified by.//
00a0: 20 20 2d 20 53 52 4d 20 36 37 39 20 44 69 76 31 - SRM 679 Div1
00b0: 20 4c 76 32 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d Lv2.//---------
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00f0: 2d 2d 2d 2d 0a 0a 69 6e 74 20 6d 61 78 5f 69 6e ----..int max_in
0100: 64 65 70 65 6e 64 65 6e 74 5f 73 65 74 28 63 6f dependent_set(co
0110: 6e 73 74 20 76 65 63 74 6f 72 3c 76 65 63 74 6f nst vector<vecto
0120: 72 3c 69 6e 74 3e 3e 26 20 47 29 0a 7b 0a 09 63 r<int>>& G).{..c
0130: 6f 6e 73 74 20 69 6e 74 20 4e 20 3d 20 47 2e 73 onst int N = G.s
0140: 69 7a 65 28 29 3b 0a 09 76 65 63 74 6f 72 3c 4c ize();..vector<L
0150: 4c 3e 20 62 61 64 6d 61 73 6b 28 47 2e 73 69 7a L> badmask(G.siz
0160: 65 28 29 29 3b 0a 09 66 6f 72 28 69 6e 74 20 76 e());..for(int v
0170: 3d 30 3b 20 76 3c 4e 3b 20 2b 2b 76 29 20 7b 0a =0; v<N; ++v) {.
0180: 09 09 4c 4c 20 78 20 3d 20 31 4c 4c 3c 3c 76 3b ..LL x = 1LL<<v;
0190: 0a 09 09 66 6f 72 28 69 6e 74 20 75 3a 20 47 5b ...for(int u: G[
01a0: 76 5d 29 0a 09 09 09 78 20 7c 3d 20 31 4c 4c 3c v])....x |= 1LL<
01b0: 3c 75 3b 0a 09 09 62 61 64 6d 61 73 6b 5b 76 5d <u;...badmask[v]
01c0: 20 3d 20 78 3b 0a 09 7d 0a 0a 09 69 6e 74 20 62 = x;..}...int b
01d0: 65 73 74 20 3d 20 30 3b 0a 09 66 75 6e 63 74 69 est = 0;..functi
01e0: 6f 6e 3c 76 6f 69 64 28 69 6e 74 2c 4c 4c 2c 69 on<void(int,LL,i
01f0: 6e 74 29 3e 20 72 65 63 20 3d 20 5b 26 5d 28 69 nt)> rec = [&](i
0200: 6e 74 20 76 2c 20 4c 4c 20 72 65 73 74 2c 20 69 nt v, LL rest, i
0210: 6e 74 20 63 75 72 29 20 7b 0a 09 09 69 66 28 62 nt cur) {...if(b
0220: 65 73 74 20 3c 20 63 75 72 29 0a 09 09 09 62 65 est < cur)....be
0230: 73 74 20 3d 20 63 75 72 3b 0a 09 09 69 66 28 72 st = cur;...if(r
0240: 65 73 74 20 3d 3d 20 30 29 0a 09 09 09 72 65 74 est == 0)....ret
0250: 75 72 6e 3b 0a 09 09 69 66 28 63 75 72 20 2b 20 urn;...if(cur +
0260: 5f 5f 62 75 69 6c 74 69 6e 5f 70 6f 70 63 6f 75 __builtin_popcou
0270: 6e 74 6c 6c 28 72 65 73 74 29 20 3c 3d 20 62 65 ntll(rest) <= be
0280: 73 74 29 0a 09 09 09 72 65 74 75 72 6e 3b 0a 0a st)....return;..
0290: 09 09 4c 4c 20 72 31 20 3d 20 72 65 73 74 20 26 ..LL r1 = rest &
02a0: 7e 20 28 31 4c 4c 3c 3c 76 29 3b 0a 09 09 4c 4c ~ (1LL<<v);...LL
02b0: 20 72 32 20 3d 20 72 65 73 74 20 26 7e 20 62 61 r2 = rest &~ ba
02c0: 64 6d 61 73 6b 5b 76 5d 3b 0a 09 09 69 66 28 72 dmask[v];...if(r
02d0: 65 73 74 20 26 20 28 31 4c 4c 3c 3c 76 29 29 20 est & (1LL<<v))
02e0: 7b 0a 09 09 09 69 66 28 72 31 20 21 3d 20 72 32 {....if(r1 != r2
02f0: 29 20 72 65 63 28 76 2b 31 2c 20 72 31 2c 20 63 ) rec(v+1, r1, c
0300: 75 72 29 3b 0a 09 09 09 72 65 63 28 76 2b 31 2c ur);....rec(v+1,
0310: 20 72 32 2c 20 63 75 72 2b 31 29 3b 0a 09 09 7d r2, cur+1);...}
0320: 20 65 6c 73 65 20 7b 0a 09 09 09 72 65 63 28 76 else {....rec(v
0330: 2b 31 2c 20 72 31 2c 20 63 75 72 29 3b 0a 09 09 +1, r1, cur);...
0340: 7d 0a 09 7d 3b 0a 09 72 65 63 28 30 2c 20 28 31 }..};..rec(0, (1
0350: 4c 4c 3c 3c 4e 29 2d 31 2c 20 30 29 3b 0a 09 72 LL<<N)-1, 0);..r
0360: 65 74 75 72 6e 20 62 65 73 74 3b 0a 7d 0a eturn best;.}.