1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Optymalizacja operacji wejścia/wyjścia
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int k;
    if (!(cin >> k)) return 0;
    int n1;
    cin >> n1;

    // Przechowujemy dane o spotkaniach z "poprzedniego" dnia
    vector<int> prev_root_day(n1 + 1, 1);
    vector<char> prev_is_leaf(n1 + 1, 1); // 1 = true, 0 = false (użycie char oszczędza kłopoty z vector<bool>)
    
    // Tablica przyrostów (tzw. diff array) do nakładania przedziałów
    vector<int> diff(k + 2, 0);

    for (int i = 2; i <= k; ++i) {
        int ni;
        cin >> ni;
        vector<int> curr_root_day(ni + 1, 0);
        vector<char> curr_is_leaf(ni + 1, 1);

        for (int j = 1; j <= ni; ++j) {
            int a;
            cin >> a;
            if (a == 0) {
                // Nowe spotkanie - początek nowej ścieżki
                curr_root_day[j] = i;
            } else {
                // Kontynuacja wcześniejszego spotkania
                curr_root_day[j] = prev_root_day[a];
                prev_is_leaf[a] = 0; // Skoro ma kontynuację, nie jest liściem
            }
        }

        // Wszystkie wierzchołki wczorajszego dnia, które nie doczekały się dzisiaj
        // kontynuacji kończą swój przedział na wczorajszym dniu (i - 1).
        for (int j = 1; j < (int)prev_root_day.size(); ++j) {
            if (prev_is_leaf[j]) {
                diff[prev_root_day[j]] += 1;
                diff[i] -= 1; // Przedział kończy się na i-1, czyli diff[(i-1) + 1] maleje
            }
        }

        // Przesuwamy stan wczorajszy na dzisiejszy (optymalizacja za pomocą std::move)
        prev_root_day = move(curr_root_day);
        prev_is_leaf = move(curr_is_leaf);
    }

    // Dodanie spotkań, które urywają się ostatecznie ostatniego dnia (dzień k)
    for (int j = 1; j < (int)prev_root_day.size(); ++j) {
        if (prev_is_leaf[j]) {
            diff[prev_root_day[j]] += 1;
            diff[k + 1] -= 1; 
        }
    }

    // Obliczenie w którym dniu nakładało się najwięcej przydziałów (algorytm gąsienicy na `diff`)
    int max_overlap = 0;
    int current_overlap = 0;
    for (int i = 1; i <= k; ++i) {
        current_overlap += diff[i];
        if (current_overlap > max_overlap) {
            max_overlap = current_overlap;
        }
    }

    // Wynik to maksymalne nałożenie na siebie obciążeń czasowych pracowników
    cout << max_overlap << "\n";

    return 0;
}