fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pi acos(-1)
  3. #define sz(x) (int) x.size()
  4. #define pii pair<int, int>
  5. #define pill pair<int, long long>
  6. #define mii map<int, int>
  7. #define vi vector<int>
  8. #define vll vector<long long>
  9. #define vs vector<string>
  10. #define vb vector<bool>
  11. #define mp make_pair
  12. #define pb push_back
  13. #define fi first
  14. #define se second
  15. #define popb pop_back
  16. #define all(v) v.begin(),v.end()
  17. #define mset(v, x) memset(v, x, sizeof(v))
  18. #define mset2d(v, x, n) memset(v, x, sizeof(v[0][0]) * n * n)
  19. #define mset2dd(v, x, n, m) memset(v, x, sizeof(v[0][0]) * n * m)
  20. #define debug(x) cerr<<#x<<" : "<<x<<endl
  21. #define debug2(x,y) cerr<<#x<<" : "<<x<<" & "<<#y<<" : "<<y<<endl
  22. #define test() cerr<<"hola papa"<<endl
  23. typedef long long ll;
  24. typedef long double ld;
  25. typedef unsigned long long ull;
  26. using namespace std;
  27.  
  28. int n, t, s;
  29. ll x;
  30.  
  31. void show(vll v) {
  32.     debug(sz(v));
  33.     for (int i = 0; i < sz(v); ++i) {
  34.         debug(v[i]);
  35.     }
  36. }
  37.  
  38. vll shared(vector< vll > v) {
  39.     map<ll, int> m;
  40.     map<ll, int>::iterator it;
  41.     vll ans;
  42.  
  43.     int li = sz(v);
  44.  
  45.     if (li == 0) {
  46.         return ans;
  47.     }
  48.  
  49.     int minsz = sz(v[0]);
  50.     int minidx = 0;
  51.  
  52.     sort(all(v[minidx]));
  53.  
  54.     for (int i = 1; i < li; ++i) {
  55.         sort(all(v[i]));
  56.  
  57.         if (sz(v[i]) < minsz) minsz = sz(v[i]), minidx = i;
  58.     }
  59.  
  60.     for (int i = 0; i < sz(v[minidx]); ++i) {
  61.         if (!m[v[minidx][i]]) {
  62.             m[v[minidx][i]] = 1;
  63.         }
  64.     }
  65.  
  66.     for (it = m.begin(); it != m.end(); ++it) {
  67.         bool found = true;
  68.  
  69.         for (int i = 0; i < li; ++i) {
  70.             if (i != minidx) {
  71.                 found = binary_search(all(v[i]), it->fi);
  72.  
  73.                 if (!found) {
  74.                     break;
  75.                 }
  76.             }
  77.         }
  78.  
  79.         if (found) {
  80.             ans.pb(it->fi);
  81.         }
  82.     }
  83.  
  84.     return ans;
  85. }
  86.  
  87. vll join(vector< vll > v) {
  88.     map<ll, int> m;
  89.     vll ans;
  90.  
  91.     int li = sz(v);
  92.  
  93.     for (int i = 0; i < li; ++i) {
  94.         int lj = sz(v[i]);
  95.  
  96.         for (int j = 0; j < lj; ++j) {
  97.             if (!m[v[i][j]]) {
  98.                 m[v[i][j]] = 1;
  99.                 ans.pb(v[i][j]);
  100.             }
  101.         }
  102.     }
  103.  
  104.     return ans;
  105. }
  106.  
  107. int main() {
  108.     cin >> n;
  109.  
  110.     vector< vll > vl;
  111.     vector< vll > vh;
  112.  
  113.     for (int i = 0; i < n; ++i) {
  114.         vll v;
  115.         cin >> t >> s;
  116.  
  117.         for (int j = 0; j < s; ++j) {
  118.             cin >> x;
  119.             v.pb(x);
  120.         }
  121.  
  122.         t == 1 ? vl.pb(v) : vh.pb(v);
  123.     }
  124.  
  125.     vll dlike = shared(vl);
  126.     vll hate = join(vh);
  127.  
  128.     vector< vll > a;
  129.     a.pb(dlike), a.pb(hate);
  130.  
  131.     vll u = join(a);
  132.  
  133.     cout << sz(u) - sz(hate) << "\n";
  134. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/FQnNov
language:
C++ (gcc 8.3)
created:
5 years 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!