Runda 6 [Hard] - Plan twierdzy

10.01.2011 - Damian Rusak

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:

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:

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Pozycja	Imię i nazwisko	Wynik	Czas	Plan twierdzy
1	Krzysztof Pszeniczny	10	07:26:15	10
2	Krzysztof Kulig	10	11:29:35	10
3	Bartosz Tarnawski	10	12:09:32	10
4	Maciej Kisiel	10	56:46:08	10
5	Krzysztof Drab	10	59:27:34	10
6	Piotr Żurkowski	10	71:34:55	10
7	Adam Czapliński	10	131:07:56	10
8	Przemysław Derengowski	10	137:30:05	10
9	Kamil Dębowski	10	144:08:04	10
10	Piotr Bejda	10	146:37:13	10
11	Bartek Dudek	10	149:15:06	10
12	Mieszko Kamyczek	10	151:21:50	10
13	Witold Długosz	10	1582:36:11	10