시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 0 | 0 | 0 | 0.000% |
W Bajtocji uruchomiono właśnie Superszybką Sieć Światłowodową. Łączy ona n domów za pomocą n - 1 kabli światłowodowych tak, że pomiędzy każdą parą domów istnieje dokładnie jedno (być może niebezpośrednie) połączenie. Ulubionym zajęciem mieszkańców Bajtocji jest kręcenie amatorskich filmów przyrodniczych, które potem umieszczają w Sieci, by pochwalić się nimi swoim przyjaciołom.
Gdy mieszkaniec i-tego domu chce pobrać film o wielkości w megabajtów umieszczony przez mieszkańca domu j, musi nawiązać połączenie między domami i oraz j o przepustowości w megabitów (Bajtocczanie są bardzo niecierpliwi). W tym celu na kablach leżących na ścieżce między tymi domami należy zarezerwować przepustowość w megabitów. Pojedynczy kabel może obsługiwać wiele połączeń, należy jednak pamiętać o tym, że ma on swoją maksymalną przepustowość.
Twoim celem jest napisanie programu, który będzie umożliwiał nawiązywanie połączeń w Sieci.
W pierwszym wierszu wejścia znajduje się liczba całkowita n (2 ≤ n ≤ 100 000) oznaczająca liczbę domów w Bajtocji. W kolejnych n wierszach znajdują się po trzy liczby całkowite ai, bi, pi (1 ≤ ai < bi ≤ n, 1 ≤ pi ≤ 1 000 000) oznaczające, że pomiędzy domami ai oraz bi istnieje kabel o przepustowości pi megabitów.
W następnym wierszu wejścia znajduje się liczba całkowita m (1 ≤ m ≤ 100 000) oznaczająca liczbę zgłoszeń do Sieci. W kolejnych m wierszach znajdują się po trzy liczby całkowite ai, bi, wi (1 ≤ ai < bi ≤ n, 0 ≤ wi ≤ 1 000 000) oznaczające zgłoszenie między domami ai oraz bi. Jeśli wi > 0, to zgłoszenie jest żądaniem nawiązania połączenia o przepustowości wi megabitów (można nawiązać kilka połączeń między daną parą domów). Dla wi = 0 zgłoszenie jest żądaniem przerwania wszystkich dotychczas nawiązanych połączeń między tymi domami.
Dla każdego żądania nawiązania połączenia należy wypisać na wyjściu jeden wiersz zawierający słowo TAK
lub NIE
, w zależności od tego, czy rezerwacja się powiodła.
8 1 2 4 2 3 8 2 4 4 4 5 9 4 6 1 4 7 5 7 8 6 10 1 8 2 3 5 3 1 8 1 3 5 1 1 8 0 3 5 3 1 3 4 7 8 7 3 4 0 4 6 1
TAK NIE TAK TAK TAK TAK NIE TAK
Camp > POI Training Camp > ONTAK 2009 4-3번