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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <cstdio>
#include <vector>

using namespace std;

int tree_size[500001];

vector<int> tree[500001];

vector<int> input[500001];

bool old[500001];

int main()
{
	int n1, k, treeCount = 0;
	scanf("%d %d", &k, &n1);
	for(int i =0;i<n1;i++)
	{
		tree_size[i] = 1;
		treeCount++;
	}

	for(int i = 0;i<k-1;i++)
	{
		int n, x;
		for(int j = 1;j <= (i==0 ? n1 : input[i-1].size());j++)
		{
			old[j] = false;
		}

		scanf("%d", &n);
		input[i].reserve(n);
		tree[i].reserve(n);
		
		for(int j = 0;j < n;j++)
		{
			scanf("%d", &x);
			input[i].push_back(x);
			
			if(x == 0)
			{
				tree_size[treeCount] = 1;
				tree[i].push_back(treeCount++);
			}
			else
			{
				if(old[x])
				{
					tree_size[i == 0 ? x-1 : tree[i-1][x-1]]++;
				}
				else
				{
					old[x] = true;
				}
				tree[i].push_back(i == 0 ? x-1 : tree[i-1][x-1]);
			}			 
		}		
	}

	int result = 0, freeEmpl = 0;
	
	for(int i = 0;i<n1;i++)
	{
		result += tree_size[i];
	}

	for(int i = 0;i<k-1;i++)
	{
		for(int j = 1;j <= (i==0 ? n1 : input[i-1].size());j++)
		{
			old[j] = false;
		}

		int neededNew = 0, newcount = 0;;
		for(int j = 0;j < input[i].size();j++)
		{
			if(input[i][j] == 0)
			{
				neededNew += tree_size[tree[i][j]];
			}
			else
			   old[input[i][j]] = true;
		}
		for(int j = 1;j <= (i==0 ? n1 : input[i-1].size());j++)
		{
			if(!old[j])
				freeEmpl ++;
		}

		freeEmpl -= neededNew;
		if(freeEmpl<0)
		{
			result -= freeEmpl;
			freeEmpl = 0;
		}

	}

	printf("%d\n", result);

	return 0;
}