You should use not the categories, but two different custom taxonomies (it’s like custom categories, if you’re not familiar with with WordPress taxonomies).
You can create two separate taxonomies via Custom Post Type UI plugin.
screenshot
And select to which of the post types, created taxonomy belongs. Also select that custom taxonomy is hierarchical, so it’s displayed like a category , not like tags.