Sachverhalt:
A.
Die einfache Gesellschaft "D._" besteht aus der E._ AG und der F._ AG. Die beiden Aktiengesellschaften bzw. die einfache Gesellschaft sind bzw. ist Eigentümerin der Parzelle 3350 an der Strasse G._ in der Gemeinde Vaz/Obervaz. Das Grundstück liegt gemäss Zonenplan in der Kernzone, wo die Ausnützungsziffer 1.0 beträgt. Das darauf stehende Gebäude weist eine anrechenbare Bruttogeschossfläche von 528.5 m2 auf und ist auf der Nordseite mit dem Gebäude auf Parzelle 3260 zusammengebaut.
A._ ist Eigentümerin der Parzelle 3265 auf der gegenüberliegenden Strassenseite, B.B_ und C.B._ sind Miteigentümer im Stockwerkeigentum an der sich ebenfalls auf der gegenüberliegenden Strassenseite befindenden Parzelle 3266.
Am 21. April 2016 bewilligte der Gemeindevorstand Vaz/Obervaz das Gesuch der einfachen Gesellschaft "D._" um Erstellung eines Ersatzneubaus auf der Parzelle 3350. Dieses Gesuch sah den Abbruch des bestehenden Gebäudes mit fünf Wohnungen und den Wiederaufbau mit vier Wohnungen und Garagen vor, teilweise im Bereich der bestehenden Altbaute. Die Baubewilligung erteilte der Gemeindevorstand mit Auflagen bezüglich Wintergärten und Vordach sowie mit einer Ausnahmebewilligung bezüglich des Strassenabstands. Die dagegen eingereichten Einsprachen von A._, B.B_ und C.B._ sowie H.H._ und I.H._ vom 3. Dezember 2015 wies der Gemeindevorstand ab.
Mit Urteil vom 22. Juni 2017 hiess das Verwaltungsgericht des Kantons Graubünden die gegen den Entscheid des Gemeindevorstands vom 21. April 2016 erhobene Beschwerde von A._ sowie B.B_ und C.B._ gut. Das Verwaltungsgericht hob den angefochtenen Bau- und Einspracheentscheid vom 21. April 2016 sowie die gleichentags erteilte Baubewilligung auf und wies die Angelegenheit zum Neuentscheid und zur Prüfung, ob für das geplante Bauvorhaben genügend Bruttogeschossfläche zur Verfügung stehe, an die Gemeinde zurück. Es führte dazu in den Erwägungen aus, der innerhalb des bisherigen Gebäudekubus gelegene Teil der Neubaute könne ohne anrechenbare Bruttogeschossfläche erstellt werden, der ausserhalb des bisherigen Gebäudekubus gelegene projektierte Gebäudeteil dürfe hingegen lediglich die zonenkonforme Ausnützungsziffer der Parzelle, mithin 335 m2 Bruttogeschossfläche, konsumieren. Ob diese Vorgaben eingehalten seien, habe die Gemeinde im Rahmen des Neuentscheids zu prüfen. Bejahendenfalls sollte die Gemeinde zudem eine Auflage betreffend Übereinstimmung der Eigentümerschaft an den jeweiligen Parkplätzen mit der zugehörigen Wohnung in die Baubewilligung aufnehmen. Die übrigen Einwände der Beschwerdeführer bezüglich Grenz- und Strassenabstand, Anzahl Parkplätze, Missachtung von Zweitwohnungsvorschriften sowie Entzug von Licht und Aussicht wurden abgewiesen.
Mit Entscheid vom 26. April 2018, mitgeteilt am 8. Mai 2018, wies die Gemeinde die Einsprache von A._ sowie B.B_ und C.B._ ab und erteilte, unter Auflagen, die Baubewilligung. Sie verwies auf das verwaltungsgerichtliche Urteil vom 22. Juni 2017 und hielt unter anderem fest, dass das Bauvorhaben die zulässige Ausnützungsziffer ausserhalb der bestehenden Gebäudehülle einhalte.
B.
Gegen diesen kommunalen Entscheid vom 26. April 2018 erhoben A._ sowie B.B_ und C.B._ mit Eingabe vom 7. Juni 2018 Beschwerde an das Verwaltungsgericht des Kantons Graubünden. Sie beantragten die kosten- und entschädigungsfällige Aufhebung des angefochtenen Entscheids sowie der Baubewilligung und die Abweisung des Baugesuchs. Zudem ersuchten sie um Erteilung der aufschiebenden Wirkung. Mit prozessleitender Verfügung vom 26. Juni 2018 erteilte der Instruktionsrichter der Beschwerde die aufschiebende Wirkung.
Mit Urteil vom 12. März 2019 trat das Verwaltungsgericht des Kantons Graubünden auf die Beschwerde nicht ein.
C.
Gegen die beiden Urteile des Verwaltungsgerichts vom 22. Juni 2017 und vom 12. März 2019 führen A._ sowie B.B_ und C.B._ am 7. Juni 2019 Beschwerde an das Bundesgericht. Sie beantragen, die beiden Urteile des Verwaltungsgerichts vom 22. Juni 2017 und vom 12. März 2019 seien aufzuheben und das Baugesuch abzuweisen.
In der Vernehmlassung nimmt die Einfache Gesellschaft "D._" mit Schreiben vom 3. September 2019 Stellung mit dem Antrag, auf die Beschwerde nicht einzutreten, eventualiter sei sie abzuweisen. Mit Schreiben vom 7. November 2019 halten die Beschwerdeführer an ihrer Beschwerde fest. Mit Schreiben vom 25. November 2019 hält die Beschwerdegegnerin an ihrer Beschwerde fest und verzichtet auf eine weitere Stellungnahme. Die Gemeinde Vaz/Obervaz hat innert Frist keine Stellungnahme eingereicht.
D.
Mit Präsidialverfügung vom 3. Juli 2019 hat das Bundesgericht dem Gesuch der Beschwerdeführer entsprochen und der Beschwerde aufschiebende Wirkung erteilt.

Erwägungen:
1.
1.1. Dem angefochtenen kantonal letztinstanzlichen Endentscheid (Art. 86 Abs. 1 lit. d und Art. 90 BGG) liegt ein Beschwerdeverfahren über eine baurechtliche Bewilligung zugrunde. Gemäss <ref-law> beurteilt das Bundesgericht Beschwerden in Angelegenheiten des öffentlichen Rechts. Dieses Rechtsmittel steht auch auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Das Bundesgerichtsgesetz enthält dazu keinen Ausschlussgrund. Nach Art. 34 Abs. 1 RPG gelten für die Rechtsmittel an die Bundesbehörden die allgemeinen Bestimmungen über die Bundesrechtspflege (<ref-ruling> E. 1.2 S. 251; <ref-ruling> E. 1.1 S. 411).
1.2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann insbesondere die Verletzung von Bundesrecht unter Einschluss des Bundesverfassungsrechts, von Völkerrecht und von kantonalen verfassungsmässigen Rechten sowie die offensichtlich unrichtige Feststellung des Sachverhalts gerügt werden (Art. 95 lit. a-c und <ref-law>). Soweit die Vorinstanz kantonales Recht anzuwenden hatte, kann im Wesentlichen geltend gemacht werden, der angefochtene Entscheid verstosse gegen Bundesrecht bzw. gegen die verfassungsmässigen Rechte und Grundsätze. Das Bundesgericht prüft kantonales Recht somit nur auf Bundesrechtsverletzung, namentlich Willkür, hin. Frei prüft es die Verletzung kantonaler verfassungsmässiger Rechte. Soweit es dabei allerdings um die Auslegung von kantonalem und kommunalem Gesetzes- und Verordnungsrecht geht, prüft dies das Bundesgericht wiederum ausschliesslich unter dem Gesichtswinkel der Willkür (<ref-ruling> E. 2 S. 149 f.).
1.3. Gemäss <ref-law> ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Der Beschwerdeführer muss sich wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzen. Besondere Anforderungen gelten, wenn die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem und kommunalem Recht) geltend gemacht wird. Dies prüft das Bundesgericht grundsätzlich nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen (<ref-ruling> E. 1.4 S. 176; <ref-ruling> E. 1.6 S. 130; <ref-ruling> E. 1.4 S. 254 f.).
2.
2.1. Zusammen mit dem kantonal letztinstanzlichen Endentscheid fechten die Beschwerdeführer das Urteil des Verwaltungsgerichts vom 22. Juni 2017 an. Streitig ist, wie dieses Urteil zu qualifizieren ist und ob es bereits in Rechtskraft erwachsen ist. Übereinstimmend mit den Beschwerdeführern gehen die Vorinstanz und die Beschwerdegegnerin davon aus, dass es sich beim Urteil des Verwaltungsgerichts vom 22. Juni 2017 um einen Rückweisungsentscheid handle. Anders als die Beschwerdeführer betonen sie jedoch, dass mit diesem Rückweisungsentscheid der Gemeindebehörde keinerlei Ermessensspielraum mehr verblieben sei, weshalb es sich dabei im Lichte der bundesgerichtlichen Rechtsprechung um einen Endentscheid handle. Entsprechend sei dieser in Rechtskraft erwachsen und nicht mehr anfechtbar.
2.2. Die Beschwerdeführer halten dem entgegen, dass das Verwaltungsgericht mit Urteil vom 22. Juni 2017 festgehalten habe, der Sachverhalt sei von der Gemeindebehörde unvollständig ermittelt worden. Das Bundesgericht wäre nicht auf eine Beschwerde dagegen eingetreten, da ein sofortiger Endentscheid nicht möglich gewesen wäre (<ref-law>) und die Streitsache zur Sachverhaltsergänzung an die Vorinstanz hätte zurückverwiesen werden müssen.
Weiter verweisen sie auf den ersten Teil des Dispositivs des Urteils des Verwaltungsgerichts vom 22. Juni 2017, welches die Entscheidungsfreiheit der Gemeinde in keiner Art und Weise einschränke. Das Dispositiv lautet:
"[1.] Die Beschwerde wird gutgeheissen, soweit darauf eingetreten wird, und der angefochtene Bau- und Einspracheentscheid vom 21. April, mitgeteilt am 5. September 2016, sowie die gleichentags erteilte Baubewilligung werden aufgehoben. Die Angelegenheit wird an die Gemeinde Vaz/Obervaz zum Neuentscheid und zur Prüfung zurückgewiesen, ob für das geplante Bauvorhaben genügend BGF [Bruttogeschossfläche] zur Verfügung steht. [...]"
Da das Verwaltungsgericht in diesem Rückweisungsentscheid offenliess, ob die Gemeinde eine Baubewilligung erteilen musste und die Einhaltung der Ausnützungsziffer nicht abschliessend überprüft werden konnte, habe es sich dabei um einen Zwischenentscheid gehandelt, gegen den auch erst zusammen mit einem später in der Sache ergangenen Endentscheid Beschwerde erhoben werden könne, wenn er sich auf diesen auswirke (<ref-law>). Solche Auswirkungen auf den Endentscheid lägen vor, da sich die Gemeinde bei der erneuten Ausstellung einer Baubewilligung und die Vorinstanz in ihrem darauf erfolgten Nichteintretensentscheid auf eine dagegen erhobene Beschwerde an die Erwägungen des ursprünglichen Rückweisungsentscheids gebunden sahen.
2.3. Rückweisungsentscheide, mit denen eine Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen wird, sind grundsätzlich Zwischenentscheide (<ref-ruling> E. 1.2 S. 148; <ref-ruling> E. 4.2 S. 481 f.). An dieser Qualifikation ändert auch nichts, wenn darin materielle Teilaspekte der Streitsache entschieden werden (vgl. <ref-ruling> E. 1.3 S. 127). Anders verhält es sich nach gefestigter Rechtsprechung des Bundesgerichts nur dann, wenn der unteren Instanz, an welche zurückgewiesen wird, kein Entscheidungsspielraum mehr verbleibt und die Rückweisung nur noch der Umsetzung des oberinstanzlich Angeordneten dient (<ref-ruling> E. 1.2 S. 148; <ref-ruling> E. 1.1 S. 143 mit Hinweisen). In diesen Ausnahmefällen lässt es das Bundesgericht zu, dass Rückweisungsbeschlüsse als (Quasi-) Endentscheide (Urteil des Bundesgerichts 2C_1076/2015 vom 9. Dezember 2016 E. 1.2.2) anfechtbar sind, obwohl sie formal als Zwischenentscheide zu qualifizieren wären (vgl. <ref-ruling> E. 1.1 S. 20). Wird von dieser Möglichkeit der Beschwerde kein Gebrauch gemacht, so sind die betreffenden Zwischenentscheide durch Beschwerde gegen den Endentscheid anfechtbar, soweit sie sich auf dessen Inhalt auswirken (<ref-law>) bzw. auswirken können.
Beim Urteil des Verwaltungsgerichts vom 22. Juni 2017 handelt es sich um einen zuvor unangefochten gebliebenen Rückweisungsentscheid. Nach dem Ausgeführten ist er als Zwischenentscheid zu qualifizieren und nach <ref-law> mit dem Endentscheid anfechtbar, soweit er sich auf dessen Inhalt auswirken kann. Das Verwaltungsgericht trat in seinem Urteil vom 12. März 2019 auf die von den Beschwerdeführern bereits in seinem Urteil vom 22. Juni 2017 behandelten Rügen mit der Begründung nicht ein, dass es sich dabei um bereits entschiedene Fragen handle. Insoweit wirkt sich sein Rückweisungsentscheid auf seinen späteren Entscheid aus. Die Beschwerde ist daher nicht nur gegen das Urteil des Verwaltungsgerichts vom 12. März 2019, sondern auch gegen jenes vom 22. Juni 2017 möglich.
2.4. Die übrigen Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde ist einzutreten.
3.
Die Beschwerdeführer bringen vor, dass die Vorinstanz die Rüge unbeurteilt liess, Art. 62 Abs. 4 des Baugesetzes der Gemeinde Vaz/ Obervaz vom 27. November 2011 (BauG) sei nicht anwendbar. Dies verstosse gegen die <ref-law>, <ref-law> und <ref-law>.
Die Vorinstanz hat ihr Urteil vom 22. Juni 2017 ausdrücklich auf Art. 62 Abs. 4 BauG abgestützt. Unzutreffend ist daher das Vorbringen, dass der betreffende Streitpunkt unbeurteilt geblieben sei. Weiter hat sie begründet, weshalb sie die Anwendbarkeit dieser Norm für gegeben hält. Dass sie in ihrem Urteil vom 12. März 2019 auf die Rüge nicht eintrat, mit der die gegenteilige Ansicht vertreten wird, verletzt das rechtliche Gehör nach <ref-law> nicht.
4.
4.1. Die Beschwerdeführer machen eine willkürliche Anwendung von Art. 62 Abs. 4 BauG geltend. Erstens habe die Vorinstanz den Ersatzneubau, der nach dem Abbruch der bestehenden Baute von Grund auf neu erstellt werde und mit dem bisherigen Gebäudevolumen nichts mehr gemeinsam habe, einem Umbau oder einer Erneuerung gleichgestellt. Zweitens sei sie davon ausgegangen, dass diese Bestimmungen auch für abgebrochene Gebäude herangezogen werden könne bzw. für Neubauten, die teilweise im Hofstattrecht nach Art. 9 Abs. 1 BauG gebaut worden seien. Drittens sei sie davon ausgegangen, dass unter bestehendem Bauvolumen auch Bauvolumen zu verstehen seien, die nicht mehr vorhanden sind, da sie abgebrochen wurden.
4.2. Nach der Praxis des Bundesgerichts verstösst ein Entscheid gegen das Willkürverbot, wenn er offensichtlich unhaltbar ist, weil er zum Beispiel eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt. Dass eine andere Lösung ebenfalls als vertretbar erscheint, genügt nicht. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch dessen Ergebnis unhaltbar ist (<ref-ruling> E. 2.2 S. 72 mit Hinweisen).
4.3. Streitig ist im Wesentlichen die Anwendung zweier kommunaler Normen, nämlich von Art. 9 Abs. 1 und Art. 62 Abs. 4 BauG.
4.3.1. Art. 9 Abs. 1 BauG stützt sich auf Art. 81 Abs. 3 des Raumplanungsgesetzes für den Kanton Graubünden (KRG/GR; BR 801.100). Nach dieser kantonalen Bestimmung können Gemeinden in ihrem Baugesetz das "Hofstattrecht" einräumen:
"Die Gemeinden können im Baugesetz auch den Wiederaufbau nach Zerstörung oder Abbruch ohne Rücksicht auf die geltenden Vorschriften der Regelbauweise für zulässig erklären (Hofstattrecht). Sie regeln die Einzelheiten unter Berücksichtigung der öffentlichen und nachbarlichen Interessen."
Die Vorinstanz hielt in ihrem Urteil vom 22. Juni 2017 fest, dass das Hofstattrecht als "besonderes Institut der Besitzstandsgarantie" bezeichnet werden könne.
Die Gemeinde Vaz/Obervaz gewährleistet das Hofstattrecht in Art. 9 Abs. 1 ihres Baugesetzes:
"Werden Bauten durch höhere Gewalt ganz oder teilweise zerstört oder zwecks Sanierung abgebrochen, dürfen sie binnen fünf Jahren im bisherigen Umfange mit den alten Gebäudemassen wieder hergestellt werden, wobei auch Zweckänderungen im Rahmen der Zonenvorschriften zulässig sind."
4.3.2. Die Vorinstanz hält fest, dass Art. 9 BauG den Wiederaufbau nach Abbruch somit bloss im bisherigen Umfang mit den alten Gebäudemassen und Zweckänderungen im Rahmen der Zonenvorschriften, unter Beachtung neuer Baulinien, Strassenabstände und Quartierpläne gestattet. Das Hofstattrecht sei als kodifizierte Ausnahmebewilligung zudem restriktiv zu handhaben.
Die Anwendbarkeit dieser Hofstattrechtsbestimmung auf den beantragten Wiederaufbau nach Abbruch binnen fünf Jahren hält die Vorinstanz für grundsätzlich erfüllt. Ein Durchdringen der alten Gebäudehülle sei zulässig, da es einem Eigentümer möglich sein müsse, seine Liegenschaft nach Zerstörung oder Abbruch ohne Rücksicht auf die geltenden Vorschriften der Regelbauweise im Hofstattrecht wieder aufzubauen und im Einklang mit den jeweils geltenden Bauvorschriften gleichzeitig die Liegenschaft auszubauen, umzubauen oder zu erweitern. Denn der Sinn des Hofstattrechts bestehe gerade darin, Eigentümer bestehender Bauten in ihrem Besitzstand zu schützen. Sie dadurch einzuschränken, dass ihnen neben einem Wiederaufbau im Hofstattrecht das Bauen im Rahmen der ordentlichen Bauvorschriften verwehrt würde, wäre widersprüchlich. Bei einem Wiederaufbau im Hofstattrecht und gleichzeitiger Erweiterung der Liegenschaft entfalte das Hofstattrecht indes nur für das altrechtliche Bauvolumen Wirkung. Auf Bauteile, die über den bisher umbauten Umfang bzw. über die bisherigen Gebäudemasse hinausgingen, sei das Hofstattrecht demgegenüber nicht anwendbar. Bei einem solchen Erweiterungsbau sei die Rechtskonformität dieser übrigen Bauteile nach der Regelbauweise und den einschlägigen Zonenvorschriften zu beurteilen. Dementsprechend prüfte die Vorinstanz in der Folge, ob diejenigen Bauteile, die über den Umfang der bisherigen Baute auf Parzelle 3350 hinausgehen würden, der Regelbauweise bzw. den Zonenvorschriften entsprächen.
4.3.3. Weshalb der geplante Bau mit gänzlich neuem, von der vorbestehenden Baute stark abweichendem Umriss als Wiederaufbau i.S.v. Art. 81 Abs. 3 KRG/GR gelten kann oder die vorbestehende Baute im bisherigen Umfang mit den alten Gebäudemassen i.S.v. Art. 9 Abs. 1 BauG "wieder herstellen" könnte, geht aus den Ausführungen der Vorinstanz nicht hervor. Ihr Hinweis darauf, dass es einem Eigentümer möglich sein müsse, seine Liegenschaft nach Zerstörung oder Abbruch ohne Rücksicht auf die geltenden Vorschriften der Regelbauweise im Hofstattrecht wieder aufzubauen und im Einklang mit den jeweils geltenden Bauvorschriften gleichzeitig die Liegenschaft auszubauen, umzubauen oder zu erweitern, lässt den im Gesetz klar verlangten Aspekt der Identität oder zumindest der weitgehenden Vergleichbarkeit der Ersatzbaute mit der vorbestehenden Baute ausser Acht. Wie bereits Art. 81 Abs. 3 KRG/GR festhält, hat die kommunale Regelung des Hofstattrechts beim Schutz des Besitzstands des Eigentümers auch die öffentlichen und nachbarlichen Interessen zu berücksichtigen. Das geschieht in Art. 9 Abs. 1 BauG gerade dadurch, dass eine Baute im Hofstattrecht nur im bisherigen Umfang und mit den alten Gebäudemassen wiederherzustellen erlaubt wird. Das bestätigt auch der Art. 2 der Ausführungsbestimmungen zum Baugesetz der Gemeinde Vaz/Obervaz vom 10. April 2002 zum Hofstattrecht nach Art. 9 BauG: Aus Art. 2 Abs. 1 der Ausführungsbestimmungen geht hervor, dass Änderungen der Gebäudeabmessungen nur innerhalb der alten Gebäudehüllen möglich sind. Auch die Kann-Vorschrift von Art. 2 Abs. 2 sieht bloss die Möglichkeit vor, eine Erweiterung der unterirdischen Gebäudeteile zuzulassen - "im Rahmen der Zonenbestimmungen" und "[w]enn es die Grenzverhältnisse zulassen". Weiter hält Art. 9 Abs. 2 BauG fest, dass Baulinien, Strassenabstände und Quartierpläne dem Hofstattrecht vorgehen. Wie auch aus Art. 2 Abs. 2 der Ausführungsbestimmungen hervorgeht, stehen selbst Änderungen innerhalb der alten Gebäudehüllen unter dem Vorbehalt, dass keine Baugestaltungslinie festgelegt ist.
Angesichts des klaren gesetzlichen Wortlauts ist es daher unhaltbar, das Hofstattrecht auf den bisherigen Gebäudekubus anzuwenden, ohne zu berücksichtigen, ob der neu geplante Bau die vorbestehende Baute im bisherigen Umfang und mit den alten Gebäudemassen wiederherstellt. Die neu geplante Baute soll unter anderem über mehr als doppelt so lange Ost- und Westfassaden verfügen und hat im Gegensatz zur bisherigen keinen kompakten, rechteckigen, sondern einen geschwungenen, langgezogenen Grundriss. Damit erfüllt sie diese gesetzlichen Anforderungen in Bezug auf die Vergleichbarkeit der Ersatzbaute mit der vorbestehenden Baute sowie in Bezug auf die Gebäudeabmessungen offensichtlich nicht.
4.4. Geplant ist die Baute in der Kernzone der Gemeinde Vaz/Obervaz. Das kommunale Baugesetz sieht für Bauten in der Kernzone in Art. 62 Abs. 4 Folgendes vor:
"Bei Umbauten und der Erneuerung bestehender, vor dem 1. Januar 1998 erstellter Bauten gilt innerhalb der bestehenden Bauvolumen keine Ausnützungsziffer."
4.4.1. Die Vorinstanz führte in ihrem Urteil vom 22. Juni 2017 aus, dass das Hofstattrecht nach Art. 9 BauG als kodifizierte Ausnahmebewilligung restriktiv zu handhaben sei, weshalb im vorliegenden Fall die Ausnützung als solche ausserhalb des bestehenden Gebäudekubus nicht besitzstandsgeschützt sei. Dementsprechend könne aber die Ausnützung im bestehenden Gebäudekubus im bisherigen Umfang mit den alten Gebäudemassen wieder verwendet werden, nicht jedoch ausserhalb des bestehenden Gebäudekubus. Indessen gelte gemäss Art. 62 Abs. 4 BauG bei Umbauten und Erneuerung bestehender, vor dem 1. Januar 1998 erstellter Bauten in der Kernzone und innerhalb der bestehenden Bauvolumen keine Ausnützungsziffer. Folglich könne der innerhalb des bisherigen Gebäudekubus gelegene Teil der Baute ohne anrechenbare Bruttogeschossfläche erstellt werden, falls das bestehende Gebäude den vorgenannten Anforderungen entspreche. Die bestehende Liegenschaft auf der Parzelle 3350 sei rechtmässig vor dem 1. Januar 1998 erstellt worden und liege in der Kernzone, weshalb der innerhalb des bisherigen Gebäudekubus gelegene Teil der geplanten Baute gestützt auf Art. 62 Abs. 4 BauG ohne anrechenbare Bruttogeschossfläche erstellt werden könne. Der ausserhalb des bisherigen Gebäudekubus gelegene projektierte Gebäudeteil dürfe dagegen lediglich die zonenkonforme Ausnützung der Parzelle 3350, mithin 335 m2 Bruttogeschossfläche, konsumieren.
4.4.2. Vorweg geht aus den Ausführungen der Vorinstanz nicht hervor, weshalb sie die geplante Baute als Umbaute oder Erneuerung im Sinne von Art. 62 Abs. 4 BauG qualifiziert. Das zu beurteilende Baugesuch sieht vor, dass das bestehende Gebäude mit fünf Wohnungen abgerissen und durch ein völlig anders beschaffenes Mehrfamilienhaus mit vier Wohnungen und Garagen ersetzt werden soll. Die Qualifikation der geplanten Baute als Umbau ist deshalb ausgeschlossen, jene als Erneuerung abwegig. In ihrem Urteil vom 22. Juni 2017 verneinte die Vorinstanz denn auch die Anwendbarkeit von Art. 81 Abs. 1 KRG/GR mit der Begründung, dass es sich bei der geplanten Baute nicht wie von jenem Gesetz vorausgesetzt um eine Erhaltung oder Erneuerung einer rechtmässig erstellten Baute oder Anlage handle. Die Rechtmässigkeit der Erstellung der vorbestehenden Baute ist unbestritten, ein Grund weshalb der Begriff der "Erneuerung" im kommunalen Baugesetz im Gegensatz zum KRG/GR derart extensiv verstanden werden dürfte, dass er einen solchen Ersatzneubau umfassen könnte, ist nicht ersichtlich.
Die Vorinstanz legt den Art. 62 Abs. 4 BauG zudem so aus, dass der innerhalb des bisherigen Gebäudekubus gelegene Teil der Baute ohne anrechenbare Bruttogeschossfläche erstellt werden könne. Demgegenüber legen auch die Ausführungsbestimmungen zum Baugesetz der Gemeinde Vaz/Obervaz vom 10. April 2002 in Art. 19 Abs. 1 zu Art. 62 Abs. 4 BauG für die Kernzone fest, dass bei "An- und Aufbauten bestehender Bauten" für die vorgesehene Erweiterung die benötigte Bruttogeschossfläche durch Ausnützungsziffer-Transport oder Zukauf sichergestellt werden muss. Die Auslegung der Vorinstanz ermöglicht es dem Eigentümer demgegenüber, den ausserhalb des bisherigen Gebäudekubus gelegenen Teil der Baute mit jener Ausnützung zu erstellen, die das Baugesetz für die gesamte, unbebaute Fläche des Grundstücks vorsehen würde. Diese Gesetzesauslegung widerspricht offensichtlich dem Sinn und Zweck einer solchen Zonenvorschrift.
4.5. Die Anwendung von Art. 9 Abs. 1 sowie Art. 62 Abs. 4 BauG auf das geplante Bauprojekt erweist sich - zumal in der Kombination - als unhaltbar.
5.
5.1. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch dessen Ergebnis unhaltbar ist (siehe E. 1.2). Es ist daher zu prüfen, ob die willkürliche Anwendung des Baugesetzes zu einem unhaltbaren Ergebnis führt.
5.2. In ihrem Urteil vom 12. März 2019 kommt die Vorinstanz zum Schluss, dass nicht gesagt werden könne, das Ergebnis ihres Urteils vom 22. Juni 2017 sei "höchst stossend" bzw. "aus jenem Urteil ergebe sich ein in höchstem Mass stossendes Ergebnis". Diesbezüglich sei nämlich darauf hinzuweisen, dass mit dem neuen zur Bewilligung eingereichten Bauprojekt mit einer Bruttogeschossfläche inner- und ausserhalb des bisherigen Gebäudekubus von 527.3 m2 sowie einer Nebenraumfläche von 166.37 m2 und Wintergärten von 63.6 m2 die ursprüngliche Bruttogeschossfläche der bestehenden Altbaute von 528.5 m2 sowie Nebenraumfläche von 167.1 m2, ohne Wintergärten, nicht überschritten werde. Die Behauptung der Beschwerdeführer, aufgrund der Ausführungen des Verwaltungsgerichts wäre eine maximale Bruttogeschossfläche von 863.5 m2 zulässig, sei "zwar rein theoretisch/mathematisch richtig", die tatsächlich projektierte und bewilligte Bruttogeschossfläche von 527.3 m2 sowie Nebenraumfläche von 166.37 m2 und Wintergärten von 63.6 m2, davon anrechenbar 13.35 m2, führe jedoch im konkreten Fall nicht zu einem in höchstem Mass stossenden Ergebnis.
5.3. Die geplante Baute mag zwar die Bruttogeschossfläche der bisherigen nicht überschreiten, doch übersteigt bereits diese ihrerseits die heute an sich zonenkonforme Ausnützung deutlich. Mit Blick auf die Besitzstandsgarantie erscheint das für sich genommen nicht unzulässig. Die geplante, zwar schmalere, gleichzeitig aber gut doppelt so lange Bauweise weicht vom Baukörper der bisherigen Baute jedoch erheblich ab und verändert damit das Bild der Kernzone massgeblich. Gerade dies will der Kernzonenschutz verhindern. Im Übrigen beeinträchtigt das Projekt auch die Aussicht der Nachbarn und bringt für sie zusätzlichen Schattenwurf mit sich, was angesichts des geltenden Bau- und Zonenrechts als zonenfremd zu beurteilen ist. Demzufolge erweist sich das Ergebnis als unhaltbar, weshalb die vorinstanzlichen Entscheide aufzuheben sind.
Bei diesem Ausgang sind die weiteren Rügen der Beschwerdeführer nicht mehr zu prüfen.
6.
Entsprechend ist die Beschwerde gutzuheissen. Die angefochtenen Entscheide sind aufzuheben und die Baubewilligung zu verweigern. Das Verwaltungsgericht des Kantons Graubünden wird die Kosten und Entschädigungen der vorinstanzlichen Verfahren neu zu verlegen haben (<ref-law>).
Bei diesem Ausgang des Verfahrens sind die Gerichtskosten der Beschwerdegegnerin bzw. ihren Gesellschaftern unter Solidarhaft aufzuerlegen (Art. 66 Abs. 1 und 5 BGG). Diese haben den anwaltlich vertretenen Beschwerdeführern eine angemessene Parteientschädigung auszurichten (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Die beiden Urteile des Verwaltungsgerichts vom 22. Juni 2017 und vom 12. März 2019 werden aufgehoben und das Baugesuch der Beschwerdegegnerin wird abgewiesen.
2.
Die Gerichtskosten von Fr. 4'000.-- werden der E._ AG und der F._ AG als Gesellschafter der einfachen Gesellschaft "D._" unter Solidarhaft auferlegt.
3.
Die E._ AG und die F._ AG als Gesellschafter der einfachen Gesellschaft "D._" haben die Beschwerdeführer für das bundesgerichtliche Verfahren unter Solidarhaft mit Fr. 4'000.-- zu entschädigen.
4.
Das Verwaltungsgericht des Kantons Graubünden wird über die Neuverlegung der Kosten und Entschädigungen der vorinstanzlichen Verfahren neu zu entscheiden haben.
5.
Dieses Urteil wird den Parteien, der Gemeinde Vaz/Obervaz und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 17. März 2020
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Der Gerichtsschreiber: Bisaz