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

[Codeforces] E. Subset Sums

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Subset Sums
Source            : Codeforces
Category          : Data Structure
Algorithm         : Heavy Light Technique
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll           long long int   
#define endl         '\n'  
  
static const int maxn = 1e5 + 5;  
static const int maxb = 320;  
  
vector <int> light_set[maxn];  
vector <int> heavy_set[maxb];  
int light_heavy_intersection[maxn][maxb];  
int heavy_heavy_intersection[maxb][maxb];  
int num_ele[maxn];  
int mapper[maxn];  
long long lazy[maxn];  
long long ans_heavy[maxn];  
long long arr[maxn];  
  
signed main()  
{  
    ios_base::sync_with_stdio(false);  
    cin.tie(nullptr);  
      
    int n, m, q;  
    cin >> n >> m >> q;  
    for (int i = 1; i <= n; i++) cin >> arr[i];  
    int light = 0;  
    int heavy = 0;  
    for (int i = 1; i <= m; i++)  
    {  
        cin >> num_ele[i];  
        if (num_ele[i] > maxb)  
        {  
            mapper[i] = ++heavy;  
            long long sum = 0;  
            heavy_set[heavy].resize(num_ele[i]);  
            for (int &x : heavy_set[heavy])   
            {  
                cin >> x;  
                sum += arr[x];        
            }  
            sort(heavy_set[heavy].begin(), heavy_set[heavy].end());  
            ans_heavy[heavy] = sum;  
        }  
        else   
        {  
            mapper[i] = ++light;  
            light_set[light].resize(num_ele[i]);  
            for (int &x : light_set[light]) cin >> x;  
            sort(light_set[light].begin(), light_set[light].end());  
        }  
    }  
    auto get = [&](vector <int> &vec, int key)  
    {  
        auto fnd = lower_bound(vec.begin(), vec.end(), key);  
        return fnd != vec.end() && *fnd == key;   
    };  
    for (int lgt = 1; lgt <= light; lgt++)  
    {  
        for (int x : light_set[lgt])  
        {  
            for (int hvy = 1; hvy <= heavy; hvy++)   
                light_heavy_intersection[lgt][hvy] += get(heavy_set[hvy], x);  
        }  
    }  
    for (int hvy = 1; hvy <= heavy; hvy++)  
    {  
        for (int x : heavy_set[hvy])  
        {  
            for (int i = 1; i <= heavy; i++) if (i != hvy)  
                heavy_heavy_intersection[hvy][i] += get(heavy_set[i], x);    
        }  
    }  
    while (q--)  
    {  
        char type;  
        cin >> type;  
        if (type == '?')  
        {  
            int x;  
            cin >> x;  
            if (num_ele[x] > maxb)  
            {  
                int hvy = mapper[x];  
                long long res = ans_heavy[hvy] + 1LL * num_ele[x] * lazy[hvy];  
                for (int i = 1; i <= heavy; i++) if (hvy != i)  
                    res += heavy_heavy_intersection[hvy][i] * lazy[i];  
                cout << res << endl;  
            }  
            else  
            {  
                int lgt = mapper[x];  
                long long res = 0;  
                for (int p : light_set[lgt]) res += arr[p];  
                for (int z = 1; z <= heavy; z++) res += (light_heavy_intersection[lgt][z] * lazy[z]);  
                cout << res << endl;  
            }  
        }  
        else   
        {  
            int x;  
            long long val;  
            cin >> x >> val;  
            if (num_ele[x] > maxb)   
            {  
                int hvy = mapper[x];  
                lazy[hvy] += val;  
            }  
            else   
            {  
                int lgt = mapper[x];  
                for (int p : light_set[lgt]) arr[p] += val;  
                for (int hvy = 1; hvy <= heavy; hvy++) ans_heavy[hvy] += (light_heavy_intersection[lgt][hvy] * val);  
            }  
        }  
    }  
}