ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1824. Ifrit Bomber

TLE 10 and WA 17
Posted by Dawid Drozd 12 Jun 2011 15:01
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
Re: TLE 10 and WA 17
Posted by ASK 5 Apr 2018 19:48
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.