Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8819

Jo'natishlar soni: 714352

Muhokama yozuvlari: 4541

Yangiliklar soni: 97

Yangiliklar izohlari: 1174


So'ngi izohlar

852. Racing on the Tree
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

Azat Yusupov hozirda TATU Urganch filiali 4-kurs talabalariga qurilmalarga dastur yozishni orgatmoqda. U yaqinda shunday bir qurilma yasadi va uni Racing on the Tree deb atadi. Bu qurilma graf korinishida, aniqrogi daraxt shaklida bolib, uning uchlari va qirralari orqali ikkita mashina harakatlanadi. Daraxtning barcha qirralari bir xil uzunlikka ega va ildizi 1-uchda joylashgan bolib mashinalar har doim ildizga tomon harakatlanadi. Mashinalar ikkita har xil a va b uchlarga qoyiladi va ularga ozgarmas va, vb (qirra / s) tezlik beriladi. Azat Yusupov 4-kurs talabalari Shavkat va Islomga bu mashinalarning qaysi biri marraga (yani ildizga) birinchi bolib yetib kelishini aniqlashni topshiriq sifatida berdi. Shavkat va Islom bu masalani osonlik bilan yechishdi. Qurilma mukammal emas edi yani bazi bir holatlarda mashinalar bir biri bilan toqnashib qolar edi. Hozirda Azat Yusupovning bu masala ustida bosh qotirishga vaqti yoq, shu sababli 4-kurs talabalarini bu muammoni ham hal qilishiga ishonmoqda. Shavkat va Islomga berilgan vazifa bu mashinalarning grafning qaysi nuqtasida uchrashishini topishdan iborat. Yani topshiriq agar mashinalar qirrada toqnashishsa qirraning tartib raqamini, uchda toqnashishsa uchning tartib raqamini topishdan iborat. Siz ham bu masalaga urinib koring balki 4-kurslarimizdan oldinroq uni yechimini toparsiz.

Kiruvchi malumotlar: Birinchi qatorda n butun soni daraxtning uchlari soni (1 ≤ n ≤ 105). Keyingi n-1 satrda ikkita butun son u va v butun sonlar i-qirraga yopishgan uchlarning tartib raqami (1 ≤ u, v n, u != v).

Keyingi qatorda q butun son sorovlar soni (1 ≤ q ≤ 105). Keyingi q ta satrda sorovlar beriladi. Har bir sorovda a, b, va, vb butun sonlar beriladi (1 ≤ a, b n, a != b, 1 ≤ va, vb ≤ 105).

Chiquvchi malumotlar: q ta satrda har bir sorov uchun bitta butun son agar mashinalar uchda uchrashishsa v x korinishda (bu yerdauchning x uchning tartib raqami), agar qirrada uchrashishsa e y korinishda (bu yerda y qirraning tartib raqami), aks holda ular uchrashishmasa n chiqaring.

Kiruvchi malumotlar

Chiquvchi malumotlar

1

10
1 2
1 3
2 4
2 5
5 6
5 7
4 8
3 9
3 10
5
8 5 7 4
6 7 1 1
6 10 3 2
4 6 4 7
2 7 1 10

e 1

v 5

v 1

e 1

e 1

2

7
1 2
1 3
3 4
3 5
5 7
2 6
6
6 5 5 5
4 7 100000 200000
3 7 1 5
7 5 300 100
3 2 9 10
6 3 4 2

v 1

v 3

e 2

e 4

n

v 1

 

Mening urinishlarim(0) Muhokama (0) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(10) Barcha urinishlar(47)