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
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Szybkie I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<int> n(k + 1);
    vector<vector<int>> adj(k + 1); // adj[dzień][numer_spotkania] = numer_poprzednika

    // 1. Wczytywanie danych
    cin >> n[1];
    for (int i = 2; i <= k; ++i) {
        cin >> n[i];
        adj[i].resize(n[i] + 1);
        for (int j = 1; j <= n[i]; ++j) {
            cin >> adj[i][j];
        }
    }

    // need[i][j] - ilu pracowników musi być na spotkaniu j w dniu i
    vector<vector<long long>> need(k + 1);
    for (int i = 1; i <= k; ++i) {
        need[i].assign(n[i] + 1, 1); // Każde spotkanie potrzebuje min. 1 osoby
    }

    // cont_sum[i][p] - suma potrzeb wszystkich kontynuacji spotkania p z dnia i
    vector<vector<long long>> cont_sum(k + 1);
    for (int i = 1; i <= k; ++i) {
        cont_sum[i].assign(n[i] + 1, 0);
    }

    // 2. Krok wstecz: Obliczamy zapotrzebowanie wynikające z kontynuacji
    for (int i = k; i >= 2; --i) {
        for (int j = 1; j <= n[i]; ++j) {
            int p = adj[i][j];
            if (p > 0) {
                cont_sum[i - 1][p] += need[i][j];
            }
        }
        for (int p = 1; p <= n[i - 1]; ++p) {
            // Spotkanie musi mieć tyle osób, by obsłużyć kontynuacje, ale min. 1
            need[i - 1][p] = max(1LL, cont_sum[i - 1][p]);
        }
    }

    // 3. Krok w przód: Liczymy minimalną liczbę pracowników
    long long total_workers = 0;
    for (int j = 1; j <= n[1]; ++j) {
        total_workers += need[1][j];
    }

    long long free_pool = 0;
    for (int i = 1; i <= k; ++i) {
        // A. Pracownicy, którzy kończą spotkania lub ich grupa się zmniejsza, idą do puli wolnych
        for (int j = 1; j <= n[i]; ++j) {
            // need[i][j] to ile osób tam było, cont_sum[i][j] to ilu MUSIAŁO iść dalej konkretną ścieżką
            free_pool += (need[i][j] - cont_sum[i][j]);
        }

        // B. Jeśli następnego dnia są spotkania ID=0, biorą pracowników z puli
        if (i < k) {
            for (int j = 1; j <= n[i + 1]; ++j) {
                if (adj[i + 1][j] == 0) {
                    long long required = need[i + 1][j];
                    if (free_pool >= required) {
                        free_pool -= required;
                    }
                    else {
                        total_workers += (required - free_pool);
                        free_pool = 0;
                    }
                }
            }
        }
    }

    cout << total_workers << endl;

    return 0;
}