Cześć mam takie zadanie:
Skrzaty
Limit pamięci: 64 MB
Zły smok Bitol najechał krainę skrzatów i wziął w niewolę jej mieszkańców. Przydzielił każdemu z n skrzatów inne stanowisko pracy i, samemu ległszy na stercie skradzionych kosztowności, jął leniwie nadzorować ich mozolne trudy.
Jako że Bitol jest wyjątkowo gnuśnym smokiem, nie obserwuje jednocześnie wszystkich poddanych. Zamiast tego cały czas przygląda się uważnie tylko skrzatom pracującym przy pewnej grupie stanowisk. W tym czasie wszystkie nieobserwowane przezeń skrzaty mogą spotykać się oraz dowolnie zamieniać się miejscami (Bitol nie jest w stanie zapamiętać, przy którym stanowisku pracował który skrzat). Co godzinę smok obraca głowę i zaczyna obserwować inny podzbiór skrzatów.
Skrzat Bajtazyl, któremu smok przydzielił stanowisko 1, chce zmobilizować towarzyszy niedoli do przeciwstawienia się Bitolowi. W tym celu musi najpierw spotkać się z sędziwym skrzatem Bajtomirem, któremu smok przydzielił stanowisko n. Przed Bajtazylem stoi zatem wyzwanie: odpowiednio zamieniając się z innymi skrzatami miejscami, winien jak najszybciej doprowadzić do sytuacji, w której on sam, ani stanowisko przy którym stoi aktualnie nasz śmiałek, ani stanowisko nie byłyby obserwowane przez smoka.
Twoim zadaniem jest ustalenie, kiedy najwcześniej może dojść do spotkania. Na szczęście wiadomo, że za godzin smok uśnie i wówczas wszystkie skrzaty będą w stanie komunikować się swobodnie.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite n i m (1 <= n, m <= 1 000 000) oznaczające odpowiednio liczbę skrzatów oraz liczbę godzin pozostałych do czasu, aż Bitol zaśnie. W następnych wierszach znajdują się opisy grup stanowisk obserwowanych przez smoka w kolejnych godzinach, po jednym w wierszu. Na opis i-tej grupy stanowisk składa się liczba całkowita ki (1 <= ki <= n) oznaczająca liczbę obserwowanych stanowisk oraz uporządkowanych rosnąco liczb całkowitych ze zbioru {1...n} oznaczających numery obserwowanych stanowisk. Wszystkie liczby w wierszu poodzielane są pojedynczymi odstępami.
Możesz założyć, że k1 + k2 +km <= 2 000 000 .
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą ze zbioru {0....m} - najmniejszą liczbę godzin, po której Bajtazyl może dotrzeć do Bajtomira.
Przykład
Dla danych wejściowych:
5 4
3 1 3 4
2 3 5
3 1 2 3
2 1 2
poprawną odpowiedzią jest:
2
Dla danych wejściowych:
6 2
4 2 3 4 5
6 1 2 3 4 5 6
poprawną odpowiedzią jest:
0
Dla danych wejściowych:
10 4
1 1
2 9 10
7 1 3 4 7 8 9 10
2 1 10
poprawną odpowiedzią jest:
4
Wyjaśnienie do przykładu:
W pierwszym z powyższych przykładów podczas pierwszej godziny swej wyprawy Bajtazyl nie może opuścić stanowiska o numerze , gdyż jest ono obserwowane przez smoka. Podczas drugiej godziny może on zamienić się miejscami ze skrzatem przy stanowisku o numerze . Dzięki temu dopiero na początku trzeciej godziny smok Bitol odwróci głowę ku stanowiskom o numerach , a Bajtazyl będzie mogł spotkać się z Bajtomirem.
W drugim z powyższych przykładów do spotkania może dojść natychmiast, gdyż w pierwszej godzinie smok nie patrzy na stanowiska Bajtazyla i Bitomira.
W trzecim przykładzie do spotkania może dojść dopiero wtedy, gdy Bitol uśnie.
I Mam taki kod
#include <bits/stdc++.h>
using namespace std;
bool can_swap(vector<bool> & possible_pos, vector<bool> & watched_pos){
for (int i = 0; i < possible_pos.size(); i++){
if (possible_pos[i] == true && watched_pos[i] == false)
return true;
}
return false;
}
void update_poss_pos(vector<bool> & possible_pos, vector<bool> & watched_pos){
for (int i = 1; i < possible_pos.size(); i++){
if (watched_pos[i] == false)
possible_pos[i] = true;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n, m, k, ans;
bool if_can_swap;
cin >> n >> m;
ans = m;
vector<bool> possible_pos(n+1, false);
possible_pos[1] = true;
vector<vector<int>> dragon_watches(m);
for (int i = 0; i < m; i++){
cin >> k;
dragon_watches[i].resize(k);
for (int j = 0; j < k; j++)
cin >> dragon_watches[i][j];
}
for (int i = 0; i < m; i++){
vector<bool> watched_pos(n+1, false);
for (int pos : dragon_watches[i])
watched_pos[pos] = true;
if_can_swap = can_swap(possible_pos, watched_pos);
if (watched_pos[n] == false && if_can_swap){
ans = i;
break;
}
if (if_can_swap)
update_poss_pos(possible_pos, watched_pos);
}
cout << ans;
return 0;
}
niestety jest za wolny dla kilku testów, próbowałem też z setami ale czasy wychodziły jeszcze gorsze, jak zoptymalizować mój algorytm >
