#include #include #include // getchar_unlocked or getchar #define getChar getchar_unlocked using namespace std; // http://www.algorytm.edu.pl/fast-i-o.html inline void wczytajLiczbe(int *liczba) { register char c = 0; register int znak_liczby = 1; while(c < 33) c = getChar(); if(c == 45) { znak_liczby = -1; c = getChar(); } (*liczba) = 0; while(c > 32) { (*liczba) = (*liczba) * 10ULL + (c - 48); c = getChar(); } (*liczba) *= znak_liczby; } // http://www.algorytm.org/algorytmy-sortowania/sortowanie-szybkie-quicksort/quick-1-c.html int partition(int tablica[], int p, int r) // dzielimy tablice na dwie czesci, w pierwszej wszystkie zbiorWyjsciowy_mapaLiczby sa mniejsze badz rowne x, w drugiej wieksze lub rowne od x { int x = tablica[p]; // obieramy x int i = p, j = r, w; // i, j - indeksy w tabeli while (true) // petla nieskonczona - wychodzimy z niej tylko przez return j { while (tablica[j] > x) // dopoki elementy sa wieksze od x j--; while (tablica[i] < x) // dopoki elementy sa mniejsze od x i++; if (i < j) // zamieniamy miejscami gdy i < j { w = tablica[i]; tablica[i] = tablica[j]; tablica[j] = w; i++; j--; } else // gdy i >= j zwracamy j jako punkt podzialu tablicy return j; } } void quicksort(int tablica[], int p, int r) // sortowanie szybkie { int q; if (p < r) { q = partition(tablica,p,r); // dzielimy tablice na dwie czesci; q oznacza punkt podzialu quicksort(tablica, p, q); // wywolujemy rekurencyjnie quicksort dla pierwszej czesci tablicy quicksort(tablica, q+1, r); // wywolujemy rekurencyjnie quicksort dla drugiej czesci tablicy } } int main() { register int n, m, k; wczytajLiczbe(&n); wczytajLiczbe(&m); wczytajLiczbe(&k); int** multizbiory = new int*[n]; int* rozmiaryMultizbiorow = new int[n]; register int rozmiarMultizbioru; int* multizbior; register int i; register int i2; register int elementMultizbioru; for(i = 0; i < n; ++i) { wczytajLiczbe(&rozmiarMultizbioru); multizbior = new int[rozmiarMultizbioru]; for(i2 = 0; i2 < rozmiarMultizbioru; ++i2) { wczytajLiczbe(&(multizbior[i2])); } quicksort(multizbior, 0, rozmiarMultizbioru - 1); rozmiaryMultizbiorow[i] = rozmiarMultizbioru; multizbiory[i] = multizbior; } register int idMultizbioru_1; register int idMultizbioru_2; map zbiorWyjsciowy_mapaLiczby; register int zbiorWyjsciowy_sumaElementow = 0; register int zbiorWyjsciowy_rozmiar = 0; register int zbiorWyjsciowy_maksymalnaWartosc = 2000000000; for(i = 0; i < k; ++i) { wczytajLiczbe(&idMultizbioru_1); wczytajLiczbe(&idMultizbioru_2); if(zbiorWyjsciowy_sumaElementow % 2 == 0) { multizbior = multizbiory[idMultizbioru_1]; rozmiarMultizbioru = rozmiaryMultizbiorow[idMultizbioru_1]; } else { multizbior = multizbiory[idMultizbioru_2]; rozmiarMultizbioru = rozmiaryMultizbiorow[idMultizbioru_2]; } for(i2 = 0; i2 < rozmiarMultizbioru; ++i2) { if(multizbior[i2] < zbiorWyjsciowy_maksymalnaWartosc || zbiorWyjsciowy_rozmiar < m) { ++zbiorWyjsciowy_rozmiar; zbiorWyjsciowy_sumaElementow += multizbior[i2]; ++zbiorWyjsciowy_mapaLiczby[multizbior[i2]]; map::reverse_iterator zbiorWyjsciowy_reverseIterator; if(zbiorWyjsciowy_rozmiar > m) // usun ostatni { zbiorWyjsciowy_reverseIterator = zbiorWyjsciowy_mapaLiczby.rbegin(); zbiorWyjsciowy_sumaElementow -= zbiorWyjsciowy_reverseIterator->first; if(zbiorWyjsciowy_reverseIterator->second > 1) // wiecej niz jedno wystapienie { --zbiorWyjsciowy_mapaLiczby[zbiorWyjsciowy_reverseIterator->first]; } else // jedno wystapienie, usun z mapy { zbiorWyjsciowy_mapaLiczby.erase(--zbiorWyjsciowy_reverseIterator.base()); } --zbiorWyjsciowy_rozmiar; } zbiorWyjsciowy_reverseIterator = zbiorWyjsciowy_mapaLiczby.rbegin(); zbiorWyjsciowy_maksymalnaWartosc = zbiorWyjsciowy_reverseIterator->first; long long int total = 0; for(map::iterator it=zbiorWyjsciowy_mapaLiczby.begin(); it!=zbiorWyjsciowy_mapaLiczby.end(); ++it) { total += it->first * it->second; } } else { break; // nastepne sa wieksze, nie wczytywac } } } register long long int total = 0; for(map::iterator it=zbiorWyjsciowy_mapaLiczby.begin(); it!=zbiorWyjsciowy_mapaLiczby.end(); ++it) { total += it->first * it->second; } cout << total << " " << zbiorWyjsciowy_mapaLiczby.size(); return 0; }