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