Az S. 129. feladat (2018. november)

S. 129. Egy város csatornahálózatát csomópontok és a csomópontok között levő csatornák alkotják. A városban összesen \(\displaystyle N\) darab csomópont van és \(\displaystyle N-1\) darab csatorna, a csatornák és csomópontok egy összefüggő hálózatot alkotnak. A csomópontok különböző magasságokban vannak, a 0 indexű csomópont van a legalacsonyabban. Egy \(\displaystyle p\) csomópont magasabban van, mint egy \(\displaystyle r\) csomópont, ha a \(\displaystyle p\) és 0 indexű csomópontok távolsága nagyobb, mint az \(\displaystyle r\) és 0 indexűeké. A lejtés miatt minden csatornában egy irányban folyik a víz, a magasabban levőtől az alacsonyabban levőig. Egy csomópontból abba a csatornába folyik a víz, amelyik a vizet egy alacsonyabban levő csomóponthoz szállítja, ha van ilyen csatorna. Ha nincs, akkor a csomópontban felgyűlik a víz, nem folyik sehova. Az előbbiekből adódik, hogy kezdetben a víz mindenhonnan a 0 indexű pontba folyik, ahol az felgyűlik. Az év során csatornák dugulnak el, ilyenkor használhatatlanok, nem folyik bennük a víz. Az eldugult csatornákat lehet, hogy megtisztítják, ilyenkor újra folyik bennük a víz. Kezdetben minden csatorna tiszta.

Georgie papírcsónakokkal játszik, a csónakot elhelyezi egy \(\displaystyle p\) indexű csomópontban. Ekkor a papírcsónak – követve a víz folyását – végül egy \(\displaystyle r\) indexű csomópontban köt ki, ahol felgyűlik a víz. Segítsünk Georgienak megtalálni ezt az \(\displaystyle r\) csomópontot.

Bemenet: Az első sorban található a csomópontok \(\displaystyle N\) és a tevékenységek \(\displaystyle Q\) száma. A következő \(\displaystyle N-1\) sorban a csomópontok indexei vannak: az \(\displaystyle i\). sorban egy \(\displaystyle j\) szám, azt jelenti, hogy az \(\displaystyle i\) és \(\displaystyle j\) indexű pontokat csatorna köti össze, amin \(\displaystyle j\) felé folyik a víz. (A 0 indexűből nem folyik sehova.) A következő \(\displaystyle Q\) sor mindegyike egy \(\displaystyle x\) és egy \(\displaystyle p\) számot tartalmaz. Ha \(\displaystyle x=1\), akkor Georgie elhelyez egy papírcsónakot a \(\displaystyle p\) csomópontnál. Ha \(\displaystyle x=0\), akkor az a csatorna, ami \(\displaystyle p\)-ből szállítja a vizet eldugul, ha eddig folyt benne a víz, vagy kitisztul, ha el volt dugulva.

Kimenet: Minden papírcsónak elhelyezés után írjuk ki (szóközzel elválasztva), hogy melyik indexű csomópontba kell mennie Georgienak, hogy megtalálja a csónakját.

Korlátok: \(\displaystyle 2\le N\le {10}^{5}\), \(\displaystyle 1\le Q\le {10}^{5}\).

Értékelés: a pontok 20%-a kapható, ha \(\displaystyle N\cdot Q\le {10}^{6}\); további 30% kapható, ha csatorna csak eldugulhat, nem tisztulhat ki; további 50% kapható az eredeti korlátokra. Időlimit: 0,5 mp.

Az I/S és S-jelű feladatok megoldását a http://mester.inf.elte.hu automatikus értékelő rendszer segítségével kipróbálhatod, tesztelheted (Téma: KöMaL - 2018/19).

(10 pont)

A beküldési határidő 2018. december 10-én LEJÁRT.

Statisztika:

8 dolgozat érkezett.
10 pontot kapott:	Csertán András, Molnár Bálint, Noszály Áron.
7 pontot kapott:	1 versenyző.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	3 versenyző.

A KöMaL 2018. novemberi informatika feladatai