#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <queue>
#include <algorithm>
#include <assert.h>
#include <set>
using namespace std;
#define ll long long
#define PB push_back
#define FOR(a,start,end) for(int a=int(start); a<int(end); a++)
#define INF INT_MAX
#define SORT(a) sort(a.begin(),a.end())
#define CL(a,x) memset(a,x,sizeof(a))
#define REP(a,x) for(int a=0;a<x;a++)
#define REP1(a,x) for(int a=1;a<=x;a++)
#define MP make_pair
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vector<ll> > vvi;
typedef vector<vector<string> > vvs;
typedef vector<pair<string, string> > vss;
typedef pair<string, string> pss;
typedef pair<ll, pii> ppii;
typedef vector<ppii> vppii;
typedef vector<vector<pii> > vvii;
typedef vector<vvi> vvvi;
ll n, k, q, d, r, g, b, z, p, a, c, m, x, h,nk;
vi vk, va, vd, vb;
vvi vva, vvk,vvd;
vii vax, vcx;
vvii vvax, vvbx;
pii p1, p2;
string w;
int ik;
int main() {
//freopen("c:\\wojtek\\uva\\pa\\debug\\18.in", "rt", stdin);
//freopen("c:\\cygwin64\\home\\plwokow\\.check_sol\\zb1\\in\\320.in", "rt", stdin);
//d = 1000000007;
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
vvk.clear();
cin >> k >> n;
vd.clear();
vk.clear();
vk.assign(n+1,0);
vvk.push_back(vk);
for (int i = 0; i < n + 1; i++)
vd.push_back(i);
vvd.push_back(vd);
n++;
nk = 1;
for (int i = 1; i < k; i++) {
cin >> a;
vk.clear();
vd.assign(a, 0);
for (int j = 0; j < a; j++) {
cin >> b;
if (b == 0)
vk.push_back(j+n);
else
vk.push_back(b+nk-1);
vd[j]=j+n;
}
vvk.push_back(vk);
vvd.push_back(vd);
nk = n;
n += a;
}
va.assign(n + 1, 0);
va[0] = 1;
d = 0;
for (int i = k - 1; i > 0; i--) {
b = 0;
for (int ik = 0; ik < vvk[i].size(); ik++) {
// if (va[vvd[i][ik]] == 0)
// b++;
// else {
b += max(1ll,va[vvd[i][ik]]);
va[vvk[i][ik]] += max(1ll,va[vvd[i][ik]]);
// }
}
d = max(d, b);
}
b = 0;
for (int ik = 0; ik < vvk[0].size(); ik++) {
if (va[vvd[0][ik]] > 0)
b += va[vvd[0][ik]];
else
b++;
}
b--;
d = max(d, b);
cout << d << '\n';
return 0;
}
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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | #include <stdio.h> #include <time.h> #include <math.h> #include <stdlib.h> #include <string.h> #include <map> #include <string> #include <vector> #include <iostream> #include <sstream> #include <queue> #include <algorithm> #include <assert.h> #include <set> using namespace std; #define ll long long #define PB push_back #define FOR(a,start,end) for(int a=int(start); a<int(end); a++) #define INF INT_MAX #define SORT(a) sort(a.begin(),a.end()) #define CL(a,x) memset(a,x,sizeof(a)) #define REP(a,x) for(int a=0;a<x;a++) #define REP1(a,x) for(int a=1;a<=x;a++) #define MP make_pair typedef vector<ll> vi; typedef pair<ll, ll> pii; typedef vector<string> vs; typedef vector<pii> vii; typedef vector<vector<ll> > vvi; typedef vector<vector<string> > vvs; typedef vector<pair<string, string> > vss; typedef pair<string, string> pss; typedef pair<ll, pii> ppii; typedef vector<ppii> vppii; typedef vector<vector<pii> > vvii; typedef vector<vvi> vvvi; ll n, k, q, d, r, g, b, z, p, a, c, m, x, h,nk; vi vk, va, vd, vb; vvi vva, vvk,vvd; vii vax, vcx; vvii vvax, vvbx; pii p1, p2; string w; int ik; int main() { //freopen("c:\\wojtek\\uva\\pa\\debug\\18.in", "rt", stdin); //freopen("c:\\cygwin64\\home\\plwokow\\.check_sol\\zb1\\in\\320.in", "rt", stdin); //d = 1000000007; std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); vvk.clear(); cin >> k >> n; vd.clear(); vk.clear(); vk.assign(n+1,0); vvk.push_back(vk); for (int i = 0; i < n + 1; i++) vd.push_back(i); vvd.push_back(vd); n++; nk = 1; for (int i = 1; i < k; i++) { cin >> a; vk.clear(); vd.assign(a, 0); for (int j = 0; j < a; j++) { cin >> b; if (b == 0) vk.push_back(j+n); else vk.push_back(b+nk-1); vd[j]=j+n; } vvk.push_back(vk); vvd.push_back(vd); nk = n; n += a; } va.assign(n + 1, 0); va[0] = 1; d = 0; for (int i = k - 1; i > 0; i--) { b = 0; for (int ik = 0; ik < vvk[i].size(); ik++) { // if (va[vvd[i][ik]] == 0) // b++; // else { b += max(1ll,va[vvd[i][ik]]); va[vvk[i][ik]] += max(1ll,va[vvd[i][ik]]); // } } d = max(d, b); } b = 0; for (int ik = 0; ik < vvk[0].size(); ik++) { if (va[vvd[0][ik]] > 0) b += va[vvd[0][ik]]; else b++; } b--; d = max(d, b); cout << d << '\n'; return 0; } |
English