[Toph] Subset of Sequences

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Subset of Sequences
Source            : Toph
Category          : Data Structure, String
Algorithm         : Trie using Map 
Verdict           : Accepted 

#include <bits/stdc++.h>  
  
using namespace std;  
  
#define ll            long long int  
#define vi            vector <int>  
  
static const int maxn = 2e6 + 5;  
static const ll mod = 1e9 + 7;  
  
int n;  
ll power[maxn], ans[maxn], length[maxn];  
  
struct Node  
{  
      ll ed;  
      map <int, Node*> Next;  
      Node()  
      {  
            ed = 0;  
            Next.clear();  
      }  
};  
  
typedef Node*     pnode;  
pnode root;  
  
void add(vi &vec)  
{  
      pnode cur = root;  
      for (int val : vec)  
      {  
            if (cur->Next.find(val) == cur->Next.end()) cur->Next[val] = new Node;  
            cur = cur->Next[val];  
            cur->ed += 1;  
      }  
}  
  
void srch(vi &vec)  
{  
      pnode cur = root;  
      int len = vec.size();  
      for (int i = 0; i < len; i++)  
      {  
            int val = vec[i];  
            if (cur->Next.find(val) == cur->Next.end()) return;  
            cur = cur->Next[val];  
            int cnt = cur->ed;  
            ans[i+1] = (ans[i+1] + (power[cnt] - 1) % mod) % mod;  
      }  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
  
      power[0] = 1;  
      for (int i = 1; i < maxn; i++) power[i] = (2LL * power[i-1]) % mod;  
  
      int n;  
      cin >> n;  
      root = new Node;  
      for (int i = 1; i <= n; i++)  
      {  
            int m;  
            cin >> m;  
            length[0]++;  
            vector <int> vec(m);  
            for (int i = 0; i < m; i++)  
            {  
                  length[i+1]++;  
                  cin >> vec[i];  
            }  
            srch(vec);  
            add(vec);  
      }  
      ans[0] = (power[ length[0] ] - 1 - length[0] + mod) % mod;  
      int q;  
      cin >> q;  
      for (int tcase = 1; tcase <= q; tcase++)  
      {  
            int k;  
            cin >> k;  
            cout << "Case " << tcase << ": " << (ans[k] + length[k]) % mod << '\n';  
      }  
}