//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
namespace debug {
template <class c> struct rge { c b, e; };
template <class c> rge<c> range(c i, c j) { return rge<c>{i, j}; }
template <class c> char spk(...);
template <class c> auto spk(c *a) -> decltype(cerr << *a, 0);
struct stream {
~stream() { cerr << endl; }
template <class c>
typename enable_if<sizeof spk<c>(0) != 1, stream &>::type operator<<(c i) {
cerr << boolalpha << i;
return *this;
}
template <class c>
typename enable_if<sizeof spk<c>(0) == 1, stream &>::type operator<<(c i) {
return *this << range(begin(i), end(i));
}
template <class a, class b> stream &operator<<(pair<a, b> p) {
return *this << "(" << p.first << ", " << p.second << ")";
}
template <class c> stream &operator<<(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; it++)
*this << ", " + 2 * (it == d.b) << *it;
return *this << "]";
}
stream &_dbg(const string &s, int i, int b) { return *this; }
template <class c, class... cs>
stream &_dbg(const string &s, int i, int b, c arg, cs... args) {
if (i == (int)(s.size()))
return (*this << ": " << arg);
b += (s[i] == '(') + (s[i] == '[') + (s[i] == '{') - (s[i] == ')') -
(s[i] == ']') - (s[i] == '}');
return (s[i] == ',' && b == 0)
? (*this << ": " << arg << " ")._dbg(s, i + 1, b, args...)
: (s[i] == ' ' ? *this : *this << s[i])
._dbg(s, i + 1, b, arg, args...);
}
};
} // namespace debug
#ifdef DEBUG
#define dout debug::stream()
#define dbg(...) ((dout << "line:" << __LINE__ << " >> ")._dbg(#__VA_ARGS__, 0, 0, __VA_ARGS__))
#else
#define dout
#define dbg(...)
#endif
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (b); i >= (a); i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define SZ(x) (int)(x).size()
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
const int MAXN = 500'007;
int N[MAXN], cnt[2][MAXN];
vi A[MAXN];
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int k;
cin >> k >> N[1];
rep(i, 2, k) {
cin >> N[i];
A[i].resize(N[i] + 1);
rep(j, 1, N[i]) cin >> A[i][j];
}
rep(i, 1, N[k]) cnt[k%2][i] = 1;
int surplus = 0;
per(i, 1, k-1) {
rep(j, 1, N[i]) cnt[i%2][j] = 0;
rep(j, 1, N[i+1]) {
if (A[i+1][j]) cnt[i%2][A[i+1][j]] += cnt[(i+1)%2][j];
else surplus += cnt[(i+1)%2][j];
}
rep(j, 1, N[i]) {
if (!cnt[i%2][j]) {
cnt[i%2][j]++;
surplus = max(0, surplus-1);
}
}
}
int ans = surplus;
rep(i, 1, N[1]) {
ans += cnt[1][i];
}
cout << ans << '\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 | //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> using namespace std; namespace debug { template <class c> struct rge { c b, e; }; template <class c> rge<c> range(c i, c j) { return rge<c>{i, j}; } template <class c> char spk(...); template <class c> auto spk(c *a) -> decltype(cerr << *a, 0); struct stream { ~stream() { cerr << endl; } template <class c> typename enable_if<sizeof spk<c>(0) != 1, stream &>::type operator<<(c i) { cerr << boolalpha << i; return *this; } template <class c> typename enable_if<sizeof spk<c>(0) == 1, stream &>::type operator<<(c i) { return *this << range(begin(i), end(i)); } template <class a, class b> stream &operator<<(pair<a, b> p) { return *this << "(" << p.first << ", " << p.second << ")"; } template <class c> stream &operator<<(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; it++) *this << ", " + 2 * (it == d.b) << *it; return *this << "]"; } stream &_dbg(const string &s, int i, int b) { return *this; } template <class c, class... cs> stream &_dbg(const string &s, int i, int b, c arg, cs... args) { if (i == (int)(s.size())) return (*this << ": " << arg); b += (s[i] == '(') + (s[i] == '[') + (s[i] == '{') - (s[i] == ')') - (s[i] == ']') - (s[i] == '}'); return (s[i] == ',' && b == 0) ? (*this << ": " << arg << " ")._dbg(s, i + 1, b, args...) : (s[i] == ' ' ? *this : *this << s[i]) ._dbg(s, i + 1, b, arg, args...); } }; } // namespace debug #ifdef DEBUG #define dout debug::stream() #define dbg(...) ((dout << "line:" << __LINE__ << " >> ")._dbg(#__VA_ARGS__, 0, 0, __VA_ARGS__)) #else #define dout #define dbg(...) #endif // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ #define rep(i, a, b) for (int i = (a); i <= (b); i++) #define per(i, a, b) for (int i = (b); i >= (a); i--) #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define all(a) (a).begin(), (a).end() #define SZ(x) (int)(x).size() #define mp make_pair #define st first #define nd second using ll = long long; using pii = pair<int,int>; using vi = vector<int>; const int MAXN = 500'007; int N[MAXN], cnt[2][MAXN]; vi A[MAXN]; int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); int k; cin >> k >> N[1]; rep(i, 2, k) { cin >> N[i]; A[i].resize(N[i] + 1); rep(j, 1, N[i]) cin >> A[i][j]; } rep(i, 1, N[k]) cnt[k%2][i] = 1; int surplus = 0; per(i, 1, k-1) { rep(j, 1, N[i]) cnt[i%2][j] = 0; rep(j, 1, N[i+1]) { if (A[i+1][j]) cnt[i%2][A[i+1][j]] += cnt[(i+1)%2][j]; else surplus += cnt[(i+1)%2][j]; } rep(j, 1, N[i]) { if (!cnt[i%2][j]) { cnt[i%2][j]++; surplus = max(0, surplus-1); } } } int ans = surplus; rep(i, 1, N[1]) { ans += cnt[1][i]; } cout << ans << '\n'; return 0; } |
English