Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP7_2I - Separatysci 3 |
Rosjanie odstąpili od swojego planu rozszczepienia systemu dróg Ukrainy na wiele części. Decyzja taka zapadła po jego dokładnym przeanalizowaniu. Ponumerowali oni miasta Ukrainy liczbami od 0 do n-1. Następnie nanieśli na mapie dokładnie n-1 dróg jakie pozostały na Ukrainie. Jak się okazało, system dróg ma postać drzewa. Z każdego miasta (wierzchołka) wychodzą co najwyżej dwie drogi (krawędzie). Wyjątkiem od tej reguły jest miejscowość o numerze 0, która to może być połączona z większą liczbą dróg.
Rosjanie szykują się do inwazji i potrzebują systemu do jej symulacji. System powinien realizować dwie operacje:
- 0 m z k zwiększa o z liczbę rosyjskich żołnierzy w mieście o numerze m oraz w każdej miejscowości oddalonej maksymalnie o k krawędzi od m.
- 1 m wyświetla aktualną liczbę rosyjskich żołnierzy znajdujących się w mieście m.
Twoim zadaniem jest oczywiście napisanie tego systemu.
Wejście
W pierwszej linii wejścia znajdują się dwie liczby całkowite n ∈ [1;100000] i o ∈ [1;600000] oznaczające odpowiednio liczbę miast na Ukrainie oraz liczbę operacji do wykonania. W kolejnych n-1 liniach znajdują się opisy dwukierunkowych dróg jakie pozostały w tym kraju. Każdy opis drogi składa się z dwóch liczb a oraz b (0 ≤ a, b < n; a ≠ b) oznaczających miasta, które łączy. W następnych o liniach znajdują się operacje do wykonania. Mogą wystąpić dwa rodzaje poleceń, które to zostały opisane w treści zadania:
- 0 m z k gdzie m ∈ [0;n), z ∈ [1;1000], k ∈ [0;n].
- 1 m gdzie m ∈ [0;n).
Wyjście
Dla każdej operacji typu 1 należy wypisać aktualną liczbę rosyjskich żołnierzy znajdujących się w wybranym mieście m.
Przykład
Wejście
7 14 0 3 2 3 1 2 6 0 4 5 0 5 0 2 5 2 1 6 1 0 1 1 0 6 10 0 0 4 10 1 0 4 5 0 1 0 1 5 1 6 1 4 0 0 100 5 1 4 1 1
Wyjście
0 5 5 5 10 10 15 115 105
Dodane przez: | Maciej Boniecki |
Data dodania: | 2015-04-11 |
Limit czasu wykonania programu: | 3s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 JS-MONKEY SCM qobi |
Pochodzenie: | VII Mistrzostwa WWSI w Programowaniu |