[Toph] Jontrona of Liakot

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Jontrona of Liakot
Source            : Toph.co
Category          : Data Structure, Graph Theory, Tree
Algorithm         : Persistent Trie
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll           long long int  
#define endl         '\n'  
  
static const int maxn = 2e5 + 5;  
static const int maxp = 6e6 + 6;  
  
struct Node  
{  
      int st;  
      int lchild;  
      int rchild;  
      Node(int st = 0, int lchild = 0, int rchild = 0)  
            : st(st)  
            , lchild(lchild)  
            , rchild(rchild) {}  
} Tree[maxp];  
  
int version[maxn];  
int NODES;  
  
int update(int root, int pos, int val)  
{  
      int newNode = ++NODES;  
      Tree[newNode] = Tree[root];  
      if (pos < 0)  
      {  
            Tree[newNode].st += 1;  
            return newNode;  
      }  
      int bit = (bool)(val & (1 << pos));  
      if (bit == 0) Tree[newNode].lchild = update(Tree[newNode].lchild, pos - 1, val);  
      else Tree[newNode].rchild = update(Tree[newNode].rchild, pos - 1, val);  
      Tree[newNode].st = Tree[ Tree[newNode].lchild ].st + Tree[ Tree[newNode].rchild ].st;  
      return newNode;  
}  
  
int kth(int root1, int root2, int root3, int root4, int pos, int k, int xor_val)  
{  
      if (pos < 0) return 0;  
      bool bit = (bool)(xor_val & (1 << pos));  
      int bad = 0;  
      if (bit == 0)  
      {  
            bad = Tree[ Tree[root4].lchild ].st - Tree[ Tree[root1].lchild ].st -  
                  Tree[ Tree[root3].lchild ].st + Tree[ Tree[root2].lchild ].st;  
            if (bad < k) return (1 << pos) + kth(Tree[root1].rchild, Tree[root2].rchild, Tree[root3].rchild, Tree[root4].rchild, pos - 1, k - bad, xor_val);  
            else return kth(Tree[root1].lchild, Tree[root2].lchild, Tree[root3].lchild, Tree[root4].lchild, pos - 1, k, xor_val);  
      }  
      else  
      {  
            bad = Tree[ Tree[root4].rchild ].st - Tree[ Tree[root1].rchild ].st -  
                  Tree[ Tree[root3].rchild ].st + Tree[ Tree[root2].rchild ].st;  
            if (bad < k) return (1 << pos) + kth(Tree[root1].lchild, Tree[root2].lchild, Tree[root3].lchild, Tree[root4].lchild, pos - 1, k - bad, xor_val);  
            else kth(Tree[root1].rchild, Tree[root2].rchild, Tree[root3].rchild, Tree[root4].rchild, pos - 1, k, xor_val);  
      }  
}  
  
vector < vector <int> > graph;  
int in[maxn];  
int out[maxn];  
int which[maxn];  
int dfsTime;  
  
void dfs(int u = 1, int p = -1)  
{  
      in[u] = ++dfsTime;  
      which[dfsTime] = u;  
      for (int v : graph[u])  
      {  
            if (v == p) continue;  
            dfs(v, u);  
      }  
      out[u] = dfsTime;  
}  
  
int arr[maxn];  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int n, q;  
      cin >> n >> q;  
      for (int i = 1; i <= n; i++) cin >> arr[i];  
      graph.resize(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);  
      }  
      dfs();  
      for (int i = 1; i <= n; i++) version[i] = update(version[i - 1], 30, arr[ which[i] ]);  
      while (q--)  
      {  
            int u, v, z, k;  
            cin >> u >> v >> z >> k;  
            int root1 = version[ in[u] - 1 ];  
            int root2 = version[ in[v] - 1 ];  
            int root3 = version[ out[v] ];  
            int root4 = version[ out[u] ];  
            int sze = out[u] - in[u] + 1 - (out[v] - in[v] + 1);  
            if (sze < k)  
            {  
                  cout << "-1" << endl;  
            }  
            else  
            {  
                  int ans = kth(root1, root2, root3, root4, 30, k, z);  
                  cout << ans << endl;  
            }  
      }  
}  

[LOJ] 1428 - Melody Comparison

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1428 - Melody Comparison
Source            : Light OJ
Category          : String, Data Structure
Algorithm         : Suffix Tree, KMP, Sparse Table
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 1e5 + 5;  
static const int inf  = 1e9 + 5;  
static const int logn = 19;  
  
struct Node  
{  
      int l;  
      int r;  
      int par;  
      int link;  
      map <char,int> next;  
      Node(int l = 0, int r = 0, int par = -1)  
            : l(l)  
            , r(r)  
            , par(par)  
            , link(-1) {}  
  
      void clean()  
      {  
            l = 0;  
            r = 0;  
            par = -1;  
            link = -1;  
            next.clear();  
      }  
      int len()  
      {  
            return r - l;  
      }  
      int &get(char c)  
      {  
            if (!next.count(c)) next[c] = -1;  
            return next[c];  
      }  
};  
  
Node t[maxn];  
string s;  
int sz;  
int n;  
  
struct state  
{  
      int v, pos;  
      state() {}  
      state(int v, int pos) : v(v), pos(pos) {}  
};  
  
state ptr;  
  
state go(state st, int l, int r)  
{  
      while (l < r)  
      {  
            if (st.pos == t[st.v].len())  
            {  
                  st = state(t[st.v].get(s[l]), 0);  
                  if (st.v == -1) return st;  
            }  
            else  
            {  
                  assert(t[st.v].l + st.pos >= 0);  
                  if (s[ t[st.v].l + st.pos ] != s[l])  
                        return state(-1, -1);  
                  if (r - l < t[st.v].len() - st.pos)  
                        return state(st.v, st.pos + r - l);  
                  l += t[st.v].len() - st.pos;  
                  st.pos = t[st.v].len();  
            }  
      }  
      return st;  
}  
  
int split(state st)  
{  
      if (st.pos == t[st.v].len())  
            return st.v;  
      if (st.pos == 0)  
            return t[st.v].par;  
      Node v = t[st.v];  
      int id = sz++;  
      t[id] = Node(v.l, v.l + st.pos, v.par);  
      t[v.par].get(s[v.l]) = id;  
      t[id].get(s[v.l + st.pos]) = st.v;  
      assert(st.v >= 0);  
      t[st.v].par = id;  
      t[st.v].l += st.pos;  
      return id;  
}  
  
int get_link(int v)  
{  
      if (t[v].link != -1)  
            return t[v].link;  
      if (t[v].par == -1)  
            return 0;  
      int to = get_link(t[v].par);  
      return t[v].link = split(go(state(to, t[to].len()), t[v].l + (t[v].par == 0), t[v].r));  
}  
  
void tree_extend(int pos)  
{  
      for(;;)  
      {  
            state nptr = go(ptr, pos, pos + 1);  
            if (nptr.v != -1)  
            {  
                  ptr = nptr;  
                  return;  
            }  
            int mid = split(ptr);  
            int leaf = sz++;  
            t[leaf] = Node(pos, n, mid);  
            t[mid].get(s[pos]) = leaf;  
            ptr.v = get_link(mid);  
            ptr.pos = t[ptr.v].len();  
            if (!mid) break;  
      }  
}  
  
void build_tree()  
{  
      sz = 1;  
      ptr = {0, 0};  
      for (int i = 0; i < maxn; i++) t[i].clean();  
      for (int i = 0; i < n; i++) tree_extend(i);  
}  
  
vector <int> longestPrefixSuffix(string &pat)  
{  
      vector <int> lps;  
      lps.push_back(0);  
      int len = pat.size();  
      int i = 1;  
      int j = 0;  
      while (i < len)  
      {  
            if (pat[i] == pat[j])  
            {  
                  i++;  
                  j++;  
                  lps.push_back(j);  
            }  
            else  
            {  
                  if (j)  
                  {  
                        j = lps[j - 1];  
                  }  
                  else  
                  {  
                        i++;  
                        lps.push_back(0);  
                  }  
            }  
      }  
      return lps;  
}  
  
int occ[maxn];  
  
void kmp(string &text, string &pat)  
{  
      int lenText = text.size();  
      for (int i = 0; i < lenText; i++) occ[i] = inf;  
      int lenPat = pat.size();  
      vector <int> lps = longestPrefixSuffix(pat);  
      int i = 0;  
      int j = 0;  
      while (i < lenText)  
      {  
            if (text[i] == pat[j])  
            {  
                  i++;  
                  j++;  
            }  
            if (j == lenPat)  
            {  
                  occ[i - 1] = i - 1;  
                  j = lps[j - 1];  
            }  
            else if (i < lenText && text[i] != pat[j])  
            {  
                  if (j) j = lps[j - 1];  
                  else i++;  
            }  
      }  
}  
  
int Table[logn][maxn];  
  
void build_sparse_table()  
{  
      for (int i = 0; i < n; i++) Table[0][i] = occ[i];  
      for (int k = 1; (1 << k) <= n; k++)  
      {  
            for (int i = 0; i + (1 << (k - 1)) < n; i++)  
            {  
                  int x = Table[k - 1][i];  
                  int y = Table[k - 1][i + (1 << (k - 1))];  
                  Table[k][i] = min(x, y);  
            }  
      }  
}  
  
int query(int i, int j)  
{  
      int k = log2(j - i + 1);  
      int x = Table[k][i];  
      int y = Table[k][j + 1 - (1 << k)];  
      return min(x, y);  
}  
  
string pat;  
int m;  
  
long long dfs(int u = 0, int sze = 0)  
{  
      long long sum = 0;  
      for (auto it : t[u].next)  
      {  
            int v = it.second;  
            int l = t[v].l;  
            int r = t[v].r - 1;  
            int need = max(0, m - sze);  
            if (t[v].len() < need)  
            {  
                  sum += t[v].len() + dfs(v, sze + t[v].len());  
            }  
            else  
            {  
                  int newl = l;  
                  int newr = r;  
                  if (need) newl = l + need - 1;  
                  int ind = query(newl, newr);  
                  if (ind == inf)  
                  {  
                        sum += t[v].len() + dfs(v, sze + t[v].len());  
                  }  
                  else  
                  {  
                        int add = max(0, ind - l);  
                        sum += add;  
                  }  
            }  
      }  
      return sum;  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            cin >> s >> pat;  
            n = s.size();  
            m = pat.size();  
            build_tree();  
            kmp(s, pat);  
            build_sparse_table();  
            cout << "Case " << tcase << ": " << dfs() << '\n';  
      }  
}