[UVA] 11183 - Teen Girl Squad

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 11183 - Teen Girl Squad
Source            : UVA Online Judge
Category          : Graph Theory
Algorithm         : Minimum Spanning Tree (Directed)
Verdict           : Accepted

#include "bits/stdc++.h"  
#include "ext/pb_ds/assoc_container.hpp"  
#include "ext/pb_ds/tree_policy.hpp"  
  
using namespace std;  
using namespace __gnu_pbds;  
  
template <typename T> using order_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;  
  
#define ll               long long int  
#define endl             '\n'  
#define pii              pair <int, int>  
  
static const int max_node = 1e3 + 5; // Maximum number of Node  
static const int max_edge = 1e5 + 5; // Maximum number of Edge  
static const int inf      = 1e9 + 9;  
  
struct Edge  
{  
      int u, v, w;  
      Edge(int u = 0, int v = 0, int w = 0)  
            : u(u), v(v), w(w) {}  
};  
  
vector <Edge> edges;  
  
int directed_mst(int root, int nv, int ne)  
{  
//      root = starting node  
//      nv   = number of nodes, starting from 0  
//      ne   = number of edges, starting from 0  
  
      vector <int> min_incoming(nv); // minimum weight among all incoming edges  
      vector <int> pre(nv);          // parent of node v  
      vector <int> cycle_id(nv);     // id of the corresponding cycle  
      vector <int> vis(nv);          // used to determine cycle  
      vector <Edge> tedges(ne);      // temporary edges, which will be changed during finding mst  
  
      tedges = edges;  
      int dmst = 0;  
      while (true)  
      {  
            for (int i = 0; i < nv; i++)  
            {  
                  min_incoming[i] = inf;  
                  cycle_id[i] = -1;  
                  vis[i] = -1;  
            }  
            for (int i = 0; i < ne; i++)  
            {  
                  int u = tedges[i].u;  
                  int v = tedges[i].v;  
                  int w = tedges[i].w;  
                  if (u != v and w < min_incoming[v]) // Taking lowest incoming edge  
                  {  
                        min_incoming[v] = w;  
                        pre[v] = u;  
                  }  
            }  
            for (int i = 0; i < nv; i++)  
            {  
                  if (i == root) continue;  
                  if (min_incoming[i] == inf) return -1; // Impossible case  
            }  
            min_incoming[root] = 0;  
            pre[root] = root; // This need to set up, or can cause infinite loop  
            int cnt_node = 0;  
            for (int i = 0; i < nv; i++)  
            {  
                  dmst += min_incoming[i];  
                  if (vis[i] == -1)  
                  {  
                        int v = i;  
                        while (vis[v] == -1)  
                        {  
                              vis[v] = i;  
                              v = pre[v];  // climbing up  
                        }  
                        if (v == root or vis[v] != i) continue;  
                        cycle_id[v] = cnt_node; // new cycle, put all the member in same id  
                        for (int u = pre[v]; u != v; u = pre[u]) cycle_id[u] = cnt_node;  
                        cnt_node++;  
                  }  
            }  
            if (cnt_node == 0) break;  
            for (int i = 0; i < nv; i++)  
            {  
                  if (cycle_id[i] == -1) cycle_id[i] = cnt_node++;  
            }  
            for (int i = 0; i < ne; i++)  
            {  
                  int tmp = tedges[i].v;  
                  tedges[i].u = cycle_id[ tedges[i].u ];  
                  tedges[i].v = cycle_id[ tedges[i].v ];  
                  if (tedges[i].u != tedges[i].v) tedges[i].w -= min_incoming[tmp];  
            }  
            nv = cnt_node;  
            root = cycle_id[root];  
      }  
      return dmst;  
}  
  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            int tnode, tedge;  
            cin >> tnode >> tedge;  
            edges.clear();  
            edges.resize(tedge);  
            for (Edge &x : edges) cin >> x.u >> x.v >> x.w;  
            int dmst = directed_mst(0, tnode, tedge);  
            cout << "Case #" << tcase << ": ";  
            if (dmst == -1) cout << "Possums!" << endl;  
            else cout << dmst << endl;  
      }  
}  

[UVA] 13092 - Fold The String

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13092 - Fold The String
Source            : UVA Online Judge
Category          : Data Structure, String
Algorithm         : Palindromic Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 3e6 + 10;  
  
struct Node  
{  
      int next[27];  
      int len;  
      int sufflink;  
      int evenLen;  
      Node(int len = 0, int sufflink = 0, int evenLen = 0)  
            : len(len)  
            , sufflink(sufflink)  
            , evenLen(evenLen)  
            {  
                  memset(next, 0, sizeof next);  
            }  
} Tree[maxn];  
  
string s;  
int len;  
int num;  
int suff;  
  
void init()  
{  
      for (int i = 0; i < maxn; i++) Tree[i] = Node();  
      num = 2;  
      suff = 2;  
      Tree[1].len = -1; Tree[1].sufflink = 1; Tree[1].evenLen = 0;  
      Tree[2].len = 0; Tree[2].sufflink = 1; Tree[2].evenLen = 0;  
}  
  
bool addLetter(int pos)  
{  
      int cur = suff;  
      int curlen = 0;  
      int let = s[pos] - 'a';  
      while (true)  
      {  
            curlen = Tree[cur].len;  
            if (pos - 1 - curlen >= 0 and s[pos - 1 - curlen] == s[pos]) break;  
            cur = Tree[cur].sufflink;  
      }  
      if (Tree[cur].next[let])  
      {  
            suff = Tree[cur].next[let];  
            return false;  
      }  
      num++;  
      suff = num;  
      Tree[num].len = Tree[cur].len + 2;  
      Tree[cur].next[let] = num;  
      if (Tree[num].len % 2 == 0) Tree[num].evenLen = Tree[num].len;  
      if (Tree[num].len == 1)  
      {  
            Tree[num].sufflink = 2;  
            return true;  
      }  
      while (true)  
      {  
            cur = Tree[cur].sufflink;  
            curlen = Tree[cur].len;  
            if (pos - 1 - curlen >= 0 and s[pos - 1 - curlen] == s[pos])  
            {  
                  Tree[num].sufflink = Tree[cur].next[let];  
                  break;  
            }  
      }  
      if (Tree[num].len % 2 == 1) Tree[num].evenLen = Tree[ Tree[num].sufflink ].evenLen;  
      return true;  
}  
  
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++)  
      {  
            int x, y;  
            cin >> x >> y >> s;  
            len = s.size();  
            init();  
            vector <int> evenLen(len);  
            for (int i = 0; i < len; i++)  
            {  
                  addLetter(i);  
                  evenLen[i] = Tree[suff].evenLen;  
            }  
            long long cost = 0;  
            for (int i = len - 1; i >= 0; i--)  
            {  
                  if (evenLen[i] > 0)  
                  {  
                        int h = evenLen[i] / 2;  
                        if (h * x > y)  
                        {  
                              cost += y;  
                              i = i - h + 1;  
                        }  
                        else  
                        {  
                              cost += x;  
                        }  
                  }  
                  else  
                  {  
                        cost += x;  
                  }  
            }  
            cout << "Case " << tcase << ": " << cost << '\n';  
      }  
}