fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define pb push_back
  5. #define all(v) v.begin(),v.end()
  6. #define rall(v) v.rbegin(),v.rend()
  7. #define sz(v) ((int)((v).size()))
  8. #define debug(x) cout << #x << " = " << x << '\n'
  9. #define Seif ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  10. #define fi(name) freopen(name ,"r",stdin)
  11. #define fo(name) freopen(name ,"w",stdout)
  12. const double PI = acos(-1);
  13. const double EPS = 1e-9;
  14. const int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
  15. const int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
  16. const int INF = 2e9+17;
  17. const int mod = 1000000007;
  18. const int N = 1e6+17;
  19. const int SQ = 320; //3e4(175), 1e5(320), 2e5(450)
  20.  
  21. void solve()
  22. {
  23.     int n; cin >> n;
  24.     vector<vector<int>> a(n);
  25.     for (int i=0; i<n; i++) {
  26.         int k; cin >> k;
  27.         while (k--) {
  28.             int x; cin >> x;
  29.             a[i].pb(x);
  30.         }
  31.         sort(all(a[i]));
  32.     }
  33.  
  34.     ll original = 0;
  35.     vector<int> mex(n), gain(N);
  36.  
  37.     for (int i=0; i<n; i++) {
  38.  
  39.         int m1 = 0, idx = 0;
  40.         while (idx < sz(a[i]) && a[i][idx]<=m1) {
  41.             if (a[i][idx] == m1) m1++;
  42.             idx++;
  43.         }
  44.  
  45.         mex[i] = m1;
  46.  
  47.         int upMex = m1+1;
  48.  
  49.         while (idx < sz(a[i]) && a[i][idx]<=upMex) {
  50.             if (a[i][idx] == upMex) upMex++;
  51.             idx++;
  52.         }
  53.  
  54.         gain[mex[i]] += upMex - mex[i];
  55.         original += mex[i];
  56.     }
  57.  
  58.  
  59.  
  60.     ll ans = 0;
  61.     for (int i=0; i<n; i++) {
  62.         for (int j=0; j<sz(a[i]); j++) {
  63.             int x = a[i][j];
  64.             bool unique = (!j || a[i][j-1]!=x) && (j+1>=sz(a[i]) || a[i][j+1]!=x);
  65.  
  66.             ans += 1LL * (n-1) * original + gain[x];
  67.             if (x < mex[i] && unique) ans -= 1LL * (n-1) * (mex[i]-x);
  68.         }
  69.     }
  70.  
  71.     cout << ans << '\n';
  72. }
  73.  
  74.  
  75. signed main() {
  76. #if !ONLINE_JUDGE
  77.     fi("input.txt");
  78.     fo("output.txt");
  79. #endif
  80.  
  81.     Seif;
  82.  
  83.     int tc; cin >> tc; while (tc--)
  84.     solve();
  85.  
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0.01s 7452KB
comments (?)
stdin
copy 
6
2
1 0
2 1 2
3
1 1
2 2 3
3 4 5 6
5
4 1 7 8 10
2 5 6
2 0 7
2 6 6
2 6 8
2
1 3
3 0 1 2
2
6 0 0 1 2 2 3
3 0 2 3
10
1 0
9 7 8 0 1 5 6 4 3 2
8 4 3 8 6 2 5 0 1
7 2 3 0 1 0 4 0
2 3 1
9 2 0 5 4 1 3 0 0 0
7 6 3 2 4 1 8 0
5 3 2 4 1 0
4 0 3 1 1
3 0 3 2
stdout
copy 
6
0
50
8
43
19202
https://ideone.com/ldv1qD
language:
C++ (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!