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
89
90
91
92
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using lld= long double;
#define v vector
#define pb  push_back
#define FF first
#define SS second
#define ALL(_) _.begin(), _.end()
v<ll>drzewo;
v<ll>spis_sum;
void spisuj(ll w){
    ll &a = spis_sum[w];
    if(a == 0) return;
    drzewo[w<<1] += a;
    drzewo[(w<<1)+1] += a;
    spis_sum[w<<1] += a;
    spis_sum[(w<<1)+1] += a;
    a = 0;
}

void dodaj(ll w, ll m_pocz, ll m_kon, ll p_pocz, ll p_kon, ll val){
    if(m_kon < p_pocz || p_kon < m_pocz) return;
    if(p_pocz <= m_pocz && m_kon <=p_kon){
        drzewo[w] += val;
        spis_sum[w] += val;
        return;
    }
    spisuj(w);
    ll mid = (m_pocz + m_kon)/2;
    dodaj(w<<1, m_pocz, mid, p_pocz, p_kon, val);
    dodaj((w<<1)+1, mid+1, m_kon, p_pocz, p_kon, val);
    drzewo[w] = max(drzewo[w<<1], drzewo[(w<<1)+1]);
}
void ustaw(ll w, ll m_pocz, ll m_kon, ll p_pocz, ll p_kon, ll val){
    if(m_kon < p_pocz || p_kon < m_pocz) return;
    if(p_pocz <= m_pocz && m_kon <=p_kon){
        drzewo[w] = val;
        return;
    }
    spisuj(w);
    ll mid = (m_pocz + m_kon)/2;
    ustaw(w<<1, m_pocz, mid, p_pocz, p_kon, val);
    ustaw((w<<1)+1, mid+1, m_kon, p_pocz, p_kon, val);
    drzewo[w] = max(drzewo[w<<1], drzewo[(w<<1)+1]);
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll ile, dl;
    cin>>ile>>dl;
    ll wielk = 1;
    while(wielk < ile) wielk <<= 1;
    drzewo.resize(wielk * 2, 0);
    spis_sum.resize(wielk*2, 0);
    //v<ll>wlk(ile);
    //wlk[0] = dl;
    ustaw(1, 0, wielk-1, 0, 0, dl);
    v<v<ll>>ptr(ile);
    ptr[0] = v<ll>(dl, 0);
    for(ll i=1;i<ile;i++){
        cin>>dl;
        ptr[i].resize(dl);
        for(ll j=0;j<dl;j++){
            cin>>ptr[i][j];
            ptr[i][j] --;
        }
        v<ll>zli(5e5, 0);
        for(ll j=0;j<dl;j++){
            if(ptr[i][j] == -1) continue;
            zli[ptr[i][j]] ++;
            if(zli[ptr[i][j]] == 1) continue;
            //dodaj(1, 0, wielk-1, ptr[i-1][ptr[i][j]], i-1, 1);
            //cerr<<"add "<<ptr[i-1][ptr[i][j]]<<"\n";
        }
        for(ll j=0;j<dl;j++){
            if(ptr[i][j] == -1){
                ptr[i][j] = i;
                continue;
            }
            if(zli[ptr[i][j]] <= 1) {                
                ptr[i][j] = ptr[i-1][ptr[i][j]];
                continue;
            }
            dodaj(1, 0, wielk-1, ptr[i-1][ptr[i][j]], i-1, zli[ptr[i][j]] -1);
            zli[ptr[i][j]] = -1;
            ptr[i][j] = ptr[i-1][ptr[i][j]];
        }
        ustaw(1, 0, wielk-1, i, i, dl);
    }
    cout<<drzewo[1]<<'\n';
}