Impostos pokemon P14748

Impostos pokemon

El professor Oak ha descobert una operació abans mai vista en el món pokemon, anomenada xor ( en C++). Il·lusionat amb aquest descobriment, li ha presentat al dictador de Kanto, al qual li ha agradat tant la idea que ha decidit imposar un nou sistema d’impostos.

Suposem el món pokemon modelat com un graf amb \(n\) pobles (vèrtexs) i \(m\) rutes (arestes bidireccionals), cadascuna de les quals etiquetada amb un natural, possiblement repetit. L’alcalde de cada poble haurà d’anar des del seu poble fins a la capital de Kanto, la Ciutat Safrà (el vèrtex 0). Per calcular quant haurà de pagar el seu poble, l’alcalde farà el xor de les etiquetes de les rutes per les quals hagi passat. Com Kanto és una regió esportista i aventurera, als alcaldes no els importarà fer un camí llarg per pagar el mínim possible, o fins i tot passar més d’una vegada pel mateix poble, la capital inclosa, o per la mateixa ruta.

Orgullós del seu nou sistema, el dictador li explica al professor Oak, i li demana que calculi quants diners rebrà, perquè ell no té ni idea de calcular xors. Però el professor Oak tampoc els controla gaire, perquè els acaba de descobrir. Podeu ajudar aquests dos dictadors a saber quants diners s’aconseguiran amb el nou impost?

Entrada

L’entrada conté diversos casos, cadascun amb \(n\) i \(m\), seguits d’\(m\) triplets \(x\) \(y\) \(\ell \), indicant una aresta entre \(x\) i \(y\) amb etiqueta \(\ell \), on \(x \ne y\). Suposeu que el graf és connex, \(2 \le n \le 1000\), \(n - 1 \le m \le 5n\), que no hi ha més d’una aresta entre cada parell de vèrtexs, i que les etiquetes es troben entre 0 i \(2^{10} - 1 = 1023\).

Sortida

Per a cada cas, escriviu la suma dels impostos aconseguits amb el nou sistema.

Pista

Considereu un graf amb \(1024 \cdot n\) vèrtexs. Eviteu fer un programa recursiu, perquè potser faria massa crides i avortaria.

Author

Víctor Conchello

© Jutge.org, 2006–2024