fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pow asdfasdf
  5.  
  6. #define FOR(i, l, r, k) for(int i = l; i<=r; i+=k)
  7. #define FOD(i, r, l, k) for(int i = r; i>=l; i-=k)
  8. #define foru(i, l, r) for(int i = l; i<=r; i++)
  9. #define fore(i, r, l) for(int i = r; i>=l; i--)
  10. #define R0F(i, a) ROF(i, 0, a)
  11. #define rep(a) F0R(_, a)
  12. #define each(a, x) for (auto &a : x)
  13.  
  14. #define iii pair<int, pair<int, int> >
  15. #define pll pair<ll, ll>
  16. #define ii pair<int, int>
  17. #define fi first
  18. #define se second
  19. #define all(v) v.begin(), v.end()
  20. #define pb push_back
  21.  
  22. #define __lcm(a, b) int((a*b)/__gcd(a, b))
  23. #define YES cout << "YES\n"
  24. #define NO cout << "NO\n"
  25.  
  26. #define bit(mask, i) ((mask>>i)&1)
  27. #define cb(mask) __builtin_popcount(mask)
  28. #define turn(mask, i) (mask ^ (1<<i))
  29.  
  30. #define int long long
  31.  
  32. typedef double db;
  33. typedef long long ll;
  34. typedef unsigned long long ull;
  35.  
  36. const int maxn = 1e5 + 5;
  37. const int maxk = 35;
  38. const int mod = 1337377;
  39. const int inf = 1e9;
  40. const int base = 311;
  41.  
  42. int n, m;
  43.  
  44. struct node
  45. {
  46.     node *a[2];
  47.     int pre;
  48.     int suf;
  49.     int d;
  50.     node()
  51.     {
  52.         d = 0;
  53.         pre = 0;
  54.         suf = 0;
  55.         FOR(i, 0, 1, 1)
  56.         {
  57.             a[i] = NULL;
  58.         }
  59.     }
  60. };
  61.  
  62. node *root;
  63.  
  64. void dfs(node *p)
  65. {
  66.     FOR(i, 0, 1, 1)
  67.     {
  68.         if(p -> a[i] != NULL)
  69.         {
  70.             p -> a[i] -> suf += p -> suf;
  71.             dfs(p -> a[i]);
  72.             p -> pre += p -> a[i] -> pre;
  73.         }
  74.     }
  75. }
  76.  
  77. signed main(){
  78.     ios_base::sync_with_stdio(0);
  79.     cin.tie(0);cout.tie(0);
  80.     root = new node();
  81.     cin >> n >> m;
  82.     FOR(i,1, n, 1)
  83.     {
  84.         node *p = root;
  85.         int k;
  86.         cin >> k;
  87.         FOR(j, 1, k, 1)
  88.         {
  89.             int x;
  90.             cin >> x;
  91.             if(p -> a[x] == NULL)p -> a[x] = new node();
  92.             p = p -> a[x];
  93.         }
  94.         p -> d ++;
  95.         p -> pre ++;
  96.         p -> suf ++;
  97.     }
  98.     dfs(root);
  99.     FOR(i, 1, m, 1)
  100.     {
  101.         bool kt = 1;
  102.         node *p = root;
  103.         int k;
  104.         cin >> k;
  105.         cout << p << "\n";
  106.         FOR(j, 1, k, 1)
  107.         {
  108.             int x;
  109.             cin >> x;
  110.             if(p -> a[x] == NULL)
  111.             {
  112.                 cout << p -> suf << "\n";
  113.                 kt = 0;
  114.                 break;
  115.             }
  116.             p = p -> a[x];
  117.         }
  118.         if(kt)
  119.         {
  120.             cout << (p -> pre) + (p -> suf) - (p -> d) << "\n";
  121.         }
  122.     }
  123.     cout << root;
  124.     return 0;
  125. }
  126.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin 
Standard input is empty
stdout 
0x55efc055eed0
https://ideone.com/YwqIFn
language:
C++14 (gcc 8.3)
created:
19 days 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!