For WA #17
IN:
6 8
13 80
17 58
92 67
57 88
96 28
65 22

OUT:
6
.....


TLE #10
IN:
30 1
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
......
0 30

Edited by author 12.06.2011 15:01

The simplest search takes 0.4s, to finish in 0.015s cut the search once it is obvious that it cannot succeed, e.g., for each city index C calculate the set of cities that must be already covered once you decided what cities before C will be targeted. In the above TLE#10 example, if you continue search starting from 3, then 1 must be already covered, that is 1 or 2 must be targeted.

BTW, bitset<N> is slightly slower than equivalent bit manipulations with int32_t, probably, because bitset uses uint64_t.