Faits:
A.
Le 2 septembre 2011, C._ s'est inscrite au chômage et un délai-cadre d'indemnisation de deux ans lui a été ouvert à partir de cette date.
Par décision du 15 décembre 2011, l'Office régional de placement de X._ (ORP) a prononcé une suspension du droit à l'indemnité de l'assurée pour une durée de 5 jours, au motif qu'elle n'avait pas remis ses recherches d'emploi du mois de novembre 2011 dans le délai légal, soit le 5 décembre 2011 au plus tard.
Après avoir pris contact avec l'ORP et lui avoir fait parvenir une copie des documents requis le 21 décembre suivant, l'assurée a formé opposition à la décision de suspension, en faisant valoir qu'elle avait déposé, comme à son habitude, ses recherches d'emploi dans la boîte aux lettres de l'ORP le 3 décembre 2011.
Le Service de l'emploi du canton de Vaud (ci-après: le service de l'emploi) a écarté l'opposition dans une nouvelle décision du 13 mars 2012.
B.
L'assurée a recouru contre cette dernière décision devant la Cour des assurances sociales du Tribunal cantonal vaudois. Dans son écriture, elle a mentionné que son mari pouvait confirmer ses dires, mais qu'elle supposait que la valeur de ce témoignage allait être relativisée en raison du lien conjugal les unissant.
Le tribunal cantonal a recueilli le témoignage du mari de l'assurée. Selon les déclarations de celui-ci, le samedi 3 décembre 2011, toute la famille était allée faire des courses ensemble et s'était ensuite rendue au bâtiment de l'ORP où C._ avait déposé l'enveloppe contenant ses recherches d'emploi dans la boîte aux lettres prévue à cet effet. L'époux de l'assurée s'en souvenait bien car la leçon de hockey de son fils avait été annulée ce samedi matin-là.
Statuant le 25 juin 2012, la juridiction cantonale a admis le recours et annulé la décision sur opposition du 13 mars 2012 ainsi que la sanction litigieuse.
C.
Le service de l'emploi interjette un recours en matière de droit public contre ce jugement, en concluant à son annulation et à la confirmation de sa décision sur opposition.
C._ conclut au rejet du recours. Le Secrétariat d'Etat à l'économie a renoncé à se déterminer.

Considérant en droit:
1.
Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si ces faits ont été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire (<ref-ruling> consid. 8.1 p. 153; <ref-ruling> consid. 1.5 p. 130, 397 consid. 1.5 p. 401) - ou en violation du droit au sens de l'<ref-law> (<ref-law>), et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>). Il incombe à la partie recourante, qui entend s'écarter des constatations de l'autorité précédente, d'expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées (<ref-ruling> consid. 1.3 p. 152, 286 consid. 1.4 et 6.2 p. 287/288).
2.
Aux termes de l'<ref-law>, aucun fait nouveau ni aucune preuve nouvelle ne peut être présenté, à moins de résulter de la décision de l'autorité précédente. La copie d'un courriel daté du 1er décembre 2011 du hockey club "Y._" que l'intimée a produite à l'appui de sa réponse ne peut donc pas être prise en considération par le Tribunal fédéral.
3.
Il est constant qu'une suspension du droit à l'indemnité d'un assuré peut être prononcée si les preuves des recherches d'emploi ne sont pas fournies dans le délai prévu par l'<ref-law> (voir <ref-ruling>).
En l'espèce, l'assurée a allégué avoir déposé le formulaire de ses recherches d'emploi (pour le mois de novembre 2011) dans la boîte aux lettres de l'ORP le 3 décembre 2011. L'ORP dit ne pas avoir reçu cette liste.
4.
Le principe inquisitoire, applicable en droit des assurances sociales, dispense les parties de l'obligation de prouver, mais ne les libère pas du fardeau de la preuve: en cas d'absence de preuve, il s'agit de savoir qui en supporte les conséquences. En matière d'indemnités de chômage, l'assuré supporte les conséquences de l'absence de preuve en ce qui concerne la remise des pièces nécessaires pour faire valoir le droit à l'indemnité, notamment la liste de recherches d'emploi (cf. arrêt C 294/99 du 14 décembre 1999 consid. 2a, in DTA 2000 n o 25 p. 122; cf. aussi arrêt 8C_427/2010 du 25 août 2010 consid. 5.1).
5.
5.1. En substance, le premier juge a considéré que les déclarations du mari de l'assurée étaient dignes de foi. Nonobstant l'écoulement du temps, celui-ci avait su relater clairement les faits de la journée du 3 décembre 2011 - soit le dépôt par sa femme de l'enveloppe contenant ses recherches d'emploi dans la boîte aux lettres de l'ORP - et expliqué de manière convaincante ce qui lui avait permis de garder en mémoire le déroulement de cette journée-là. Dès lors que les dires de l'assurée se trouvaient ainsi confirmés, le premier juge a admis que la preuve du respect du délai de l'<ref-law> était rapportée au degré de la vraisemblance requise.
5.2. Le recourant invoque une violation du droit et une appréciation arbitraire des preuves. Il estime que la remise en temps utile des recherches d'emploi doit être établie non pas au degré de la vraisemblance prépondérante mais avec certitude. En outre, le tribunal cantonal avait fait preuve d'arbitraire en retenant que le témoignage de l'époux de l'assurée permettait de prouver la remise en temps utile des recherches d'emploi de cette dernière. Tout d'abord, le Tribunal fédéral avait déjà dit que le dépôt d'une enveloppe dans une boîte aux lettres était un acte anodin ne laissant généralement aucun souvenir précis au témoin de cet acte à moins que l'attention de ce dernier n'ait été spécialement attirée sur ce fait pour en rapporter la preuve ultérieurement (arrêt C 360/97 du 14 décembre 1998). Ensuite, le témoin était conjoint de l'assurée et avait un intérêt financier manifeste à l'issue positive du litige. Enfin, l'intimée n'avait mentionné le moyen de preuve par témoin qu'au stade de la procédure cantonale.
6.
6.1. En l'occurrence, on ne voit pas en quoi le premier juge aurait violé le droit. Celui-ci a correctement retenu que le fardeau de la preuve du respect du délai incombait à l'assurée. Par ailleurs, le recourant ne prétend pas, à juste titre, que le témoignage du conjoint de l'intimée serait un moyen de preuve irrecevable au regard du droit de procédure administrative cantonale.
6.2. Le recourant conteste en revanche la valeur probante de ce témoignage remettant ainsi en cause la constatation des faits et l'appréciation des preuves par la juridiction cantonale sur lesquelles, comme on l'a dit plus haut (voir consid. 1 supra), le Tribunal fédéral n'exerce qu'un contrôle restreint.
L'appréciation des preuves est arbitraire lorsqu'elle est manifestement insoutenable, en contradiction avec le dossier, ou contraire au sens de la justice et de l'équité ou lorsque l'autorité ne tient pas compte, sans raison sérieuse, d'un élément propre à modifier la décision, se trompe sur le sens et la portée de celui-ci ou, se fondant sur les éléments recueillis, en tire des constatations insoutenable (<ref-ruling> consid. 4.3 p. 62 et les références).
Les motifs avancés par le recourant ne permettent pas de remettre en cause l'appréciation du témoignage du mari de l'assurée. La jurisprudence à laquelle il se réfère (arrêt C 360/97 du 14 décembre 1998) concerne le cas d'un témoignage donné deux ans après les faits. Or, la déposition du mari ne remonte pas aussi loin dans le temps et on peut penser que la notification de la décision de suspension, à peine deux semaines après qu'il eut accompagné sa femme à la boîte aux lettres de l'ORP, lui a permis de garder en mémoire ce fait précis. Ensuite, que l'intimée n'ait pas mentionné ce moyen de preuve avant la procédure cantonale peut se comprendre par le fait que celle-ci croyait à tort que le témoignage de son époux ne serait pas recevable. Enfin, la circonstance que le témoin est conjoint de l'intimée permet certes d'envisager une convergence d'intérêts. Cela étant, elle n'exclut pas d'emblée que la déposition soit tenue pour digne de foi. Le tribunal cantonal en a d'ailleurs tenu compte et expliqué les raisons pour lesquelles il accordait néanmoins crédit au témoignage de l'époux. Ce point de vue est défendable et s'inscrit dans le pouvoir d'appréciation du juge cantonal quoi qu'en pense le recourant, même si la solution contraire n'aurait pas non plus été insoutenable. Il échappe par conséquent au grief de l'arbitraire.
6.3. Dans la mesure où le recourant échoue à démontrer que la constatation déterminante de la décision attaquée procède d'une appréciation arbitraire des preuves, le Tribunal n'a aucune raison de s'en écarter. Le recours est mal fondé.
7.
Bien que le service de l'emploi succombe, il n'y a pas lieu de prélever des frais judiciaires (<ref-law>; <ref-ruling> consid. 4.5 p. 642).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté.
2.
Il n'est pas perçu de frais de justice.
3.
Le présent arrêt est communiqué aux parties, au Tribunal cantonal du canton de Vaud, Cour des assurances sociales, et au Secrétariat d'Etat à l'économie (SECO).
Lucerne, le 29 juillet 2013
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
La Présidente: Leuzinger
La Greffière: von Zwehl