Runda 6 [Hard] - Plan twierdzy

10.01.2011 - Damian Rusak
TrudnośćTrudność

 

Zadanie tygodnia

Runda 6; kategoria Hard

Limit czasowy: 2s; Limit pamięciowy: 64MB


Plan twierdzy

Zaiste nadeszły ciężkie czasy. Nad naszym królestwem zawisła groźba inwazji nieprzyjaciela. Rozpoczęto już budowę murów obronnych, które mają chronić ludność (a przede wszystkim najważniejszych królewskich urzędników) przed wrogiem.

Ty, królewski architekt, masz za zadanie czuwać nad przebiegiem prac. Tymczasem $ k $ najważniejszych osób w królestwie chciałoby schronić się już za murami. Nie godzą się na opuszczenie dworu króla nim wszyscy nie otrzymają bezpiecznych miejsc do przeczekania inwazji. Wszyscy na dworze króla spiskują i nienawidzą się wzajemnie. Każdy z nich postawił warunek, że ma znajdować się w innej bezpiecznej części niż reszta. Bezpieczną częścią nazwiemy każdy minimalny fragment królestwa ogrodzony murami obronnymi. (Minimalny w tym kontekście to taki, który w swoim wnętrzu nie zawiera żadnej innej bezpiecznej części - na ilustracji są to fragmenty otoczone przez mury o numerach 1,4,5,9 oraz o numerach 2,5,6,7,9).

Znasz dokładnie plan budowy - wiesz, w jakiej kolejności mury zostaną ukończone i że żadne dwa nie zostaną ukończone w tym samym czasie. Odpowiedz możnym na ich pytanie - po którym zbudowanym murze będą mogli najwcześniej wszyscy schronić się w różnych bezpiecznych częściach królestwa?

Wejście:

Pierwsza linia wejścia zawiera liczby naturalną $ n $ i $ k $ - liczbę fragmentów murów obronnych oraz liczbę ważnych urzędników króla. ($ 1 \leq n,k \leq 10^{6} $). W kolejnych $ n $ liniach znajdują się opisy murów w kolejności w jakiej zostaną ukończone - czwórki liczb całkowitych $ a_{i}, b_{i}, c_{i}, d_{i} $ oznaczające, że $ i $-ty fragment muru to odcinek łączący punkty $ (a_{i}, b_{i}) $ $ (c_{i}, d_{i}) $ $ (0 \leq a_{i},b_{i},c_{i},d_{i} \leq 10^{6}) $. Odcinki nie przecinają się, a jedynymi ich wspólnymi punktami mogą być ich końce.

Wyjście:

Wyjście winno składać się z jednej liczby całkowitej $ m $ ($ 1 \leq m \leq n $) - najmniejszego numeru muru po którego ukończeniu istnieć będzie przynajmniej $ k $ bezpiecznych części królestwa. Jeśli taka liczba nie istnieje, należy wypisać $ -1 $.

Przykład 1:

Wejście:

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

Wyjście:

9

Przykład 2:

Wejście:

5 1
1 1 5 6
4 3 8 3
10 10 11 11
0 1 1 7
13 4 15 15

Wyjście:

-1

Przykład 3:

Wejście:

7 2
0 0 5 5
5 5 5 0
5 0 0 0
1 1 3 3
3 3 3 1
3 1 1 1
0 0 0 3
Wyjście:

6

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasPlan twierdzy
1Krzysztof Pszeniczny1007:26:1510
2Krzysztof Kulig1011:29:3510
3Bartosz Tarnawski1012:09:3210
4Maciej Kisiel1056:46:0810
5Krzysztof Drab1059:27:3410
6Piotr Żurkowski1071:34:5510
7Adam Czapliński10131:07:5610
8Przemysław Derengowski10137:30:0510
9Kamil Dębowski10144:08:0410
10Piotr Bejda10146:37:1310
11Bartek Dudek10149:15:0610
12Mieszko Kamyczek10151:21:5010
13Witold Długosz101582:36:1110
5
Twoja ocena: Brak Ocena: 5 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com