#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; } int main() { register int n, m, k; wczytajLiczbe(&n); wczytajLiczbe(&m); wczytajLiczbe(&k); map* multizbiory = new map[n]; int* rozmiaryMultizbiorow = new int[n]; map* multizbior; register int rozmiarMultizbioru; register int liczba; register int i; register int i2; register int elementMultizbioru; for(i = 0; i < n; ++i) { wczytajLiczbe(&rozmiarMultizbioru); multizbior = new map(); for(i2 = 0; i2 < rozmiarMultizbioru; ++i2) { wczytajLiczbe(&liczba); ++(*multizbior)[liczba]; } multizbiory[i] = *multizbior; } register int idMultizbioru_1; register int idMultizbioru_2; register long long int zbiorWyjsciowy_sumaElementow = 0; register int zbiorWyjsciowy_rozmiar = 0; register int zbiorWyjsciowy_maksymalnaWartosc = 2000000000; register int wartoscElementu; map zbiorWyjsciowy_mapaLiczby; map::reverse_iterator zbiorWyjsciowy_reverseIterator; map::iterator it; for(i = 0; i < k; ++i) { wczytajLiczbe(&idMultizbioru_1); wczytajLiczbe(&idMultizbioru_2); if(zbiorWyjsciowy_sumaElementow % 2 == 0) { multizbior = &multizbiory[idMultizbioru_1]; } else { multizbior = &multizbiory[idMultizbioru_2]; } for(it=multizbior->begin(); it!=multizbior->end(); ++it) { wartoscElementu = it->first; for(i2 = 0; i2 < it->second; ++i2) { if(wartoscElementu < zbiorWyjsciowy_maksymalnaWartosc || zbiorWyjsciowy_rozmiar < m) { ++zbiorWyjsciowy_rozmiar; zbiorWyjsciowy_sumaElementow += wartoscElementu; ++zbiorWyjsciowy_mapaLiczby[wartoscElementu]; 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; } else { break; // nastepne sa wieksze, nie wczytywac } } } } cout << zbiorWyjsciowy_sumaElementow << " " << zbiorWyjsciowy_mapaLiczby.size(); return 0; }