[Toph] B. Dictionary Tree

 

Problem Link    : B. Dictionary Tree
Category        : Trie, Tree, Dfs
Contest         : Intra AIUB Programming Contest 2024 (Senior)

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
struct Trie {
    int counter;
    Trie *child[26];
    Trie *parent;
 
    Trie() {
        counter = 0;
        parent = nullptr;
        for (int i = 0; i < 26; i++) {
            child[i] = nullptr;
        }
    }
    ~Trie() {
        for (int i = 0; i < 26; i++) {
            if (child[i] and this != child[i]) {
                delete child[i];
            }
        }
    }
};
 
typedef Trie* pnode;
pnode root;
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = true; string FILE = "in.txt";
    if (FILEIO and fopen(FILE.c_str(), "r")) {
        freopen(FILE.c_str(), "r", stdin);
    }
 
    int n, k;
    cin >> n >> k;
    vector<vector<int>> graph(n + 1);
    for (int e = 1; e < n; e++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<char> letters(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> letters[i];
    }
    for (int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end(), [&](int x, int y)
            {
               return letters[x] < letters[y];
            });
    }
    root = new Trie();
    pnode curRoot = root;
    function<void(int, int)> Dfs = [&](int u, int p) {
        if (curRoot->child[ letters[u] - 'a' ] == nullptr) {
            curRoot->child[ letters[u] - 'a' ] = new Trie();
            curRoot->child[ letters[u] - 'a' ]->parent = curRoot;
            curRoot = curRoot->child[ letters[u] - 'a' ];
            curRoot->counter++;
        } else {
            curRoot->child[ letters[u] - 'a' ]->parent = curRoot;
            curRoot = curRoot->child[ letters[u] - 'a' ];
            curRoot->counter++;
        }
        for (int v : graph[u]) {
            if (v == p) {
                continue;
            }
            Dfs(v, u);
        }
        curRoot = curRoot->parent;
    };
    Dfs(1, 0);
    string path = "";
    function<void(pnode)> Solve = [&](pnode rt) {
        if (rt == nullptr) {
            return;
        }
        if (k <= 0) {
            cout << path << endl;
            exit(0);
        }
        for (int i = 0; i < 26; i++) {
            if (rt->child[i] == nullptr) {
                continue;
            }
            path += static_cast<char>(i + 'a');
            k -= rt->child[i]->counter;
            Solve(rt->child[i]);
            path.pop_back();
        }
    };
    Solve(root);
}

[Hackerearth] Special Subarrays

 

Problem Link    : Special Subarrays
Category        : Trie
Contest         : DSA Coding Contest - January '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
template <const int32_t MOD> struct modint {
    int32_t value;
    modint() = default;
    modint(int32_t value_) : value(value_) {}
    inline modint<MOD> operator + (modint<MOD> other) const { int32_t c = this->value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); }
    inline modint<MOD> operator - (modint<MOD> other) const { int32_t c = this->value - other.value; return modint<MOD>(c <    0 ? c + MOD : c); }
    inline modint<MOD> operator * (modint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); }
    inline modint<MOD> & operator += (modint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline modint<MOD> & operator -= (modint<MOD> other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; }
    inline modint<MOD> & operator *= (modint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
    inline modint<MOD> operator - () const { return modint<MOD>(this->value ? MOD - this->value : 0); }
    modint<MOD> pow(uint64_t k) const { modint<MOD> x = *this, y = 1; for (; k; k >>= 1) { if (k & 1) y *= x; x *= x; } return y; }
    modint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
    inline modint<MOD> operator /  (modint<MOD> other) const { return *this *  other.inv(); }
    inline modint<MOD> operator /= (modint<MOD> other)       { return *this *= other.inv(); }
    inline bool operator == (modint<MOD> other) const { return value == other.value; }
    inline bool operator != (modint<MOD> other) const { return value != other.value; }
    inline bool operator < (modint<MOD> other) const { return value < other.value; }
    inline bool operator > (modint<MOD> other) const { return value > other.value; }
};
template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value) * n; }
template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; }
template <int32_t MOD> istream & operator >> (istream & in, modint<MOD> &n) { return in >> n.value; }
template <int32_t MOD> ostream & operator << (ostream & out, modint<MOD> n) { return out << n.value; }
 
const int mod = 1e9 + 7;
using mint = modint<mod>;
 
struct Trie {
    int ones;
    Trie *child[2];
 
    Trie() {
        ones = 0;
        for (int i = 0; i < 2; i++) {
            child[i] = nullptr;
        }
    }
    ~Trie() {
        for (int i = 0; i < 2; i++) {
            if (child[i] and this != child[i]) {
                delete child[i];
            }
        }
    }
};
 
typedef Trie* pnode;
pnode root;
 
void add(string &s) {
    pnode curRoot = root;
    for (char ch : s) {
        int val = ch - '0';
        if (curRoot->child[val] == nullptr) {
            curRoot->child[val] = new Trie();
        }
        curRoot = curRoot->child[val];
    }
}
 
mint ans;
 
void dfs(pnode curRoot, int ones) {
    for (int i = 0; i < 2; i++) {
        if (curRoot->child[i]) {
            int nones = ones + (i == 0);
            ans += max(0ll, nones - 1);
            dfs(curRoot->child[i], nones);
        }
    }
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    int n;
    cin >> n;
    root = new Trie();
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        add(s);
    }
    ans = 0;
    dfs(root, 0);
    cout << ans << endl;
}

[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';  
      }  
}