Cześć, podsyłam małą paczkę z testami (po 10 do każdego z podzadań). Nie gwarantuję, że outy są poprawne, ale wejścia powinny być w porządku.

Link: http://1drv.ms/1Gpq0go

Outy mi się zgadzają :)

potwierdzam outy

Potwierdzam

Potwierdzam

Potwierdzam

Pięć testów ode mnie: http://1drv.ms/1OJbLX4

PS. Duże testy, sprawdzi ktoś?
PS. Jestem prawie pewien, że outy są błędne, postaram się naprawić asap.

Potwierdzam testy Kamila.
@Maciej Nadolski, twoje testy nie są zgodne ze specyfikacją wejścia.

Rozumiem, że specyfikacja wejścia zakłada, że może istnieć najwyżej jedno skrzyżowanie, od którego odchodzi != 2 dróg?

@Przemysław Czerwiński, co dokładnie jest nie tak z testami bo nie mogę się dopatrzyć błędu.. Może źle treść zrozumiałem?
@Michał Wityk, z tego co ja rozumiem to nie, np.
8 10
1 2
2 3
3 1
3 4
4 5
5 6
6 3
6 7
7 8
8 6
Jeśli dobrze rozumiem treść to takie wejście też jest poprawne mimo tego, że ze skrzyżowań 3 i 6 wychodzą po 4 drogi

@Maciej Nadolski

http://scr.hu/0h70/a6gyp

Widzę to tak. Jeżeli Twój program radzi sobie bez takiego założenia, to ogromny szacun, bo wydaje mi się, że jest ono konieczne, aby uniknąć złożoności zbliżonej do O(n^2). Z resztą czytałem o grach parzystości i taka naturalna, bez założeń, jest naprawdę ciężka do rozpatrzenia.
(mam nadzieję, że nie piszę za dużo)

@edit
Dobra, widzę już, że to jednak zielone łamie założenie, bo "centralne" skrzyżowanie jest odwiedzane dwukrotnie.

Zgadzam się z Maćkiem. Testy sprawdzę najwcześniej jutro, algorytm jest, myślę działający, ale programu nie, a dosyć wolno kodzę.

Bo wydaje mi się po prostu, że w testach w 1 poście wychodzi się z założenia, że zawsze jest jeden korytarz, który ma dostęp do wszystkich ewentualnych pętli, ale jak się teraz zastanowić, to wcale tak nie musi być. Dobra, na razie nic nie wniosę do dyskusji, bo i jeszcze nie mam gotowego rozwiązania by sprawdzić rzetelnie te testy.

Czy mógłby ktoś wrzucić jakąś większą paczkę? Zwłaszcza fajnie byłoby gdyby wszystkie "pętle" były stosunkowo małe, np. max 6 długości, takie testy mają (wg mnie) największą szansę wykrycia ewentualnych błędów, będą też najmniej przyjemne dla niektórych brutów.

@Kamil Kaznowski Właśnie takie są te moje testy - wszystkie pętle mają długość 3 albo 4 oprócz jednej, która może mieć trochę więcej. Sprawdziłeś może ich poprawność? Jeśli jednak są w porządku to mogę wygenerować więcej...

"Kończę" debugować, do jutra rana potwierdzę ;)

Dobra, faktycznie źle przeanalizowałem to założenie. A miało być tak pięknie ._.
Edit: Heura analizująca tylko przypadki z jednym "środkiem" raczej dostanie 0, co nie?

Też myślałem na początku, że będą to "kwiatki". W ogóle jak u Was z czasami na tych testach, spodziewacie się tu 100 punktów? Szkoda, że hydepark jest dość martwy, bo (na tyle, na ile nie łamiemy zasad) można by było powymieniać się subiektywnymi rankingami zadań pod względem trudności i tak dalej. Bo mi tutaj na tych największych testach samo załadowanie wejścia potrafi ponad sekundę-dwie zająć.


@Przemysław Czerwiński
Wiesz, wszystkie testy ocen jak i te pierwsze właśnie biorą to założenie i zapewne wprowadziło to Ciebie, mnie i pewnie wiele osób w to błędne myślenie. Natomiast myślę, że punkty da się jeszcze nazbierać.

W ogóle to nie wiem, czy przy przydzielaniu punktów za podzadanie można dostać jakieś punkty, jeśli program dobrze zrobił tylko część testów z tego podzadania? I czy w podzadaniach na bardzo duże wejście mimo wszystko mogą trafić się testy z małymi wejściami, z których w takiej sytuacji dałoby się nazbierać parę punktów nawet wolniejszym programom?

@ Michał Wityk "Bo mi tutaj na tych największych testach samo załadowanie wejścia potrafi ponad sekundę-dwie zająć"
Jakim cudem?
TU PRZYPOMNIENIE / WSKAZÓWKA DLA KORZYSTAJĄCYCH Z IOSTREAM!!!!!
Pamiętajcie o dodawaniu "magicznej linijki" na początku programu:
ios_base::sync_with_stdio(false);
Dzięki niej operacje wczytywania / wypisywania cin /cout działają około 3-4 razy szybciej.
Samo wczytanie danych nie powinno przekraczać w żadnym przypadku 0,5 sekundy.

Ups, wybaczcie - moje testy-"kwiatki" narobiły trochę zamieszania. Macieju - wielkie dzięki za wyprowadzenie mnie z błędu. =)

No cóż, trzeba się jeszcze trochę pogłowić...

https://drive.google.com/file/d/0BzTEEO9t3TyKTExGdDBjREplcm8/view?usp=sharing

testy losowe i zrobione na szybko, więc całkiem możliwe, że są błędne.

1-500: n,m <= 20
501-1000: n,m <= 1000

EDIT: poprawiłem testy, mam nadzieję, że tym razem będą poprawne :P
EDIT2: jednak nadal błędne

@Kamil Kaznowski
Właśnie z tego korzystam, no takie z tych pierwszych testów po 800k wierszy nieco ponad sekundę szły.
ios_base::sync_with_stdio(false);
cin >> skrzyzowan >> drog;
for(int i = 1; i <= drog; i++)
{
cin >> do_tablicy >> do_tablicy;
}
a tak się zaczyna main, więc sam nie wiem, może to coś u mnie, może na sio zadziała lepiej. Nie podałem struktury danych by nikt mnie przypadkiem nie zdyskwalifikował.


==================================
Notka od moderatora:
Proszę nie publikować możliwych wskazówek dot. trudności zadań oraz podzadań.

@Michał Wityk
Podzadania nie są ze sobą powiązane, tj. nie muszą być (więc zapewne nie będą) ograniczone innymi podzadaniami. Jeśli chodzi o testy, to nawet jeśli w jakimś będą małe dane pomimo innych specyfikacji wynikających z danego podzadania, to będzie on zgrupowany z innymi, większymi testami. Więc nie licz na to, że zdobędziesz więcej punktów, niż tyle, ile dają ci podzadania, dla których twój program działa poprawnie.

@Michał Tepper, w niektórych (nie wszystkich) testach jest podana nieprawidłowa liczba dróg (hyd1.in):
19 20
1 2
1 7
2 3
3 4
4 5
5 6
6 7
7 8
7 14
8 9
9 10
10 11
11 12
12 13
13 14
5 15
5 19
15 16
16 17
17 18
18 19

@Michał Wityk
Z reguły, niestety, na sio2 zwykle działa gorzej ;)
Można sobie poszukać oitimetool - przygotowanie do działania jest nieco mozolne, ale pokazuje praktycznie identyczny czas, jaki będzie na sio2.

=======================
Notka od moderatora:
Proszę nie publikować możliwych wskazówek dot. trudności zadań oraz podzadań.

@Kamil Kaznowski
I powiem też, że mam sporo access violationów w testach @Maciej Nadolski.

=======================
Notka od moderatora:
Proszę nie publikować możliwych wskazówek dot. trudności zadań oraz podzadań.

@Michał
Podczas debugowania, zwłaszcza gdy odpalasz w konsoli jakiegoś środowiska to akurat może być normalne :) Jeśli z flagą -O2/-O3 przy np. przekazywaniu wejścia z pliku tak jest, to wtedy rzeczywiście coś musi być nie tak.

@Michał Tepper
Wydaje mi się, że w tym teście (w niektórych innych też mam inaczej)
17 20
1 2
1 5
2 3
3 4
4 5
2 6
2 8
6 7
7 8
2 9
2 15
9 10
10 11
11 12
12 13
13 14
14 15
7 16
7 17
16 17
Poprawna odpowiedź to (pisząc w jednej linijce):
11111212212121211
a nie:
12111222222222211
Rozrysowałem sobie na kartce i tak mi wyszło.

Potwierdzam testy Kamila, nie potwierdzam Michała.

Dorzucam od siebie kilka testów, chyba troszeczkę ciekawszych.

1-200 - n,m <= 20
201-250 - n,m <= 500000

https://drive.google.com/file/d/0B7LTbx-1p1SAajYwSlVDbWZRNjA/view?usp=sharing

Nie potwierdzam testów Mateusza:
Pierwsza różnica - 3 test, 14 linijka, powinno być 2