I'm sure it's possible to go even faster than that, but you'd have to be really lucky and just happen to stumble upon all the AI with your early galleys. Realistically, I think anyone would struggle to find some of the random island colonies.Actually 300-400 AD is possible. I had kept too many cities and they were taken back by stray archers and could not find a Mongol City placed 8 tiles away from my capital. I spent about 8 galley's with two Preat each looking for this city instead of killing off the remaining two cives.
Razing cities was the way to go. Except my game took so long, I had to raze 2 or even 3 cities in the same spots.

Well, tbh, I don't think I had construction by your victory date.By the way if you are willing to loose a few units, cats are not needed. I never learned Construction

When I got to Hattie's main island, her capital had 5-ish combat axes to go with half a dozen archers @ 60%. A turn of bombardment and some catapult attacks let me preserve all my praets for Mansa, instead of losing 4-5 and potentially falling just short. The supply line was long at that point. That said, I was actually just commenting on the fact that cats kill units...