Glasovanje

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 256 MB
Avtor:
  • Tomaž Hočevar
  • UPM

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

V parlamentu se bliža glasovanje za sprejem novega zakona o računalniških tekmovanjih, ki bo določil dovoljene programske jezike. Kot si lahko predstavljate, je to precej kontroverzna tematika. Stranke imajo različno število poslancev, vsi poslanci iste stranke pa glasujejo enako. Na začetku vsaka stranka podpira ali pa nasprotuje zakonu. Splošno znano dejsto je, da politiki radi spreminjajo svoja stališča, zato se v dneh pred glasovanjem stranke v parih ali trojicah srečujejo na sestankih.

Cilj sestanka je vedno uskladitev mnenj. Kadar imajo vse stranke enako mnenje, je sestanek pretežno družabne narave. Če pa se mnenja razlikujejo, ena od strank najprej ustrezno prilagodi svoje mnenje:

  • Če sta na sestanku dve stranki, se druga stranka prilagodi mnenju prve.
  • Če so na sestanku tri stranke, se prilagodi tista stranka, ki ima drugačno mnenje od preostalih dveh.

Poleg tega na sestankih med dvema strankama stranki vedno podpišeta pogodbo o trajnem sodelovanju. To pomeni, da bodo njuni poslanci zagotovo vedno glasovali enako.

Kadar na sestanku neka stranka X spremeni mnenje, to ogrozi pogodbe, ki jih je sklenila pred tem. Ker pa je njeno novo mnenje sveže pridobljeno in je zato X še polna entuziazma, to mnenje vedno uspešno prenese na vse preostale stranke, s katerimi je v preteklosti sklenila trajno sodelovanje. Te stranke svoje novo mnenje nato prenesejo na stranke, s katerimi so sodelovanje sklenile one, in tako naprej.

Preberi opis sestankov, kot so se odvijali po vrsti, in izračunaj, koliko glasov ZA in koliko PROTI bo prejel zakon na dan glasovanja, po koncu vseh sestankov.

Vhodni podatki

Prva vrstici vsebuje število strank N in število sestankov M. Zaradi enostavnosti bomo stranke označevali s števili od 1 do N. Druga vrstica vsebuje število glasov G_i strank od 1 do N. i-to število v tretji vrstici je enako 0, če stranka na začetku nasprotuje zakonu in 1, če ga podpira. Sledi M vrstic, ki vsebujejo 2 ali 3 števila, ki predstavljajo stranke, ki sodelujejo na sestanku.

Omejitve vhodnih podatkov

  • 1 \leq N, M \leq 10^5
  • 1 \leq G_i \leq 1000

Izhodni podatki

Izpiši s presledkom ločeni števili glasov ZA in PROTI.

Primer

Vhod

6 4
2 3 1 7 2 1
0 1 0 0 1 1
2 4
1 2 3
2 1
5 6 4

Izhod

15 1

Komentar

Po prvem sestanku postane stranka 4 ZA.
Po drugem sestanku postane stranka 2 PROTI. Ker je pred tem sklenila sodelovanje s stranko 4, postane tudi 4 PROTI.
Tretji sestanek ne prinese sprememb mnenj, le stranki 2 in 1 skleneta sodelovanje.
Po četrtem sestanku postane stranka 4 ZA. Ker je pred tem sklenila sodelovanje s stranko 2, postane tudi 2 ZA. Ker je 2 pred tem sklenila sodelovanje z 1, postane tudi 1 ZA.

Na koncu je torej samo stranka 3 (ki ima enega samega člana) PROTI, ostale (ki imajo skupaj 15 članov) pa so ZA.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task