HackerEarth Nick and JosephLand problem solution

In this HackerEarth Nick and JosephLand problem solution Nick is the mayor of JosephLand. He wants to make a reform of the roads in JosephLand. In JosephLand, there are n cities, numbered 1 through n. There are also m weighted, directed roads represented by three numbers:

•  ui vi wi: there is a road from ui to vi and the fine taken on this road is wi. That means, if you pass a road from vi to ui, i.e violating the traffic law you have to pay wi coins, otherwise you don't have to pay anything.

Nick is going to have a travel. Travel consists of q journeys. Each journey is represented by two numbers: ai,bi. That means, he starts his journey in ai and ends in bi. Every time he will choose a journey with minimum cost. Cost of a journey is equal to the sum of fines he paid during the journey.

Consumption of a travel is Summation(j=1,q) cost(j). As Nick is the mayor of JosephLand, before the travel he can change directions of any roads as many times as he wants. So now Nick wants to change directions of some roads in such a way, that consumption is minimal. Note that no changes can be made.

HackerEarth Nick and JosephLand problem solution.

#include <bits/stdc++.h>

#define pb push_back
#define pp pop_back
#define mp make_pair
#define ld long double
#define f first
#define s second
#define ll long long

using namespace std;

const int N = 5e5 + 5;

const int mod = 1e9 + 7;

int n, m, q, c[N], fup[N], tin[N], timer, tout[N], used[N], sz[N], p[N], s[N], e[N], t[N], up[20][N];

ll ans;

vector < pair < int, int > > g[N];

unordered_map < int, bool > is_bridge[N];

unordered_map < int, int > C[N];

struct edge
{
  int from, to, cost;
} a[N], b[N];

void dfs(int v = 1)
{
  used[v] = 1;
  tin[v] = fup[v] = ++timer;
  for (auto to : g[v])
  {
    if (to.f == p[v]) continue;
    if (used[to.f]) fup[v] = min(fup[v], tin[to.f]);
    else
    {
      p[to.f] = v;
      dfs(to.f);
      fup[v] = min(fup[v], fup[to.f]);
      if (fup[to.f] > tin[v] && C[v][to.f] == 1) 
      {
       is_bridge[v][to.f] = is_bridge[to.f][v] = 1;
      }
    }
  }
}

void dfs(int v, int C)
{
  c[v] = C;
  sz[C]++;
  for (auto to : g[v])
  {
    if (is_bridge[v][to.f]) continue;
    if (!c[to.f]) dfs(to.f, C);
  }
}

int P(int a, int b)
{
  return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b)
{
  if (P(a, b)) return a;
  if (P(b, a)) return b;
  for (int i = 19;i >= 0;i--)
  {
    int x = up[i][a];
    if (x > 0 && !P(x, b)) a = x;
  }
  return up[0][a];
}

void go(int v = 1)
{
  tin[v] = ++timer;
  up[0][v] = p[v];
  for (int i = 1;i < 20;i++) up[i][v] = up[i - 1][up[i - 1][v]];
  for (auto to : g[v])
  {
    if (to.f != p[v])
    {
      p[to.f] = v;
      go(to.f);
    }
  }
  tout[v] = timer;
}

void calc(int v = 1)
{
  for (auto to : g[v])
    if (to.f != p[v])
    {
      calc(to.f);
      s[v] += s[to.f];
      e[v] += e[to.f];
      t[v] += t[to.f];
      int down_up = s[to.f] - t[to.f];
      int up_down = e[to.f] - t[to.f];
      ans += 1ll * to.s * min(down_up, up_down);
    }
}
    
int main()
{
  ios_base::sync_with_stdio(0);
  
  cin >> n >> m;
  for (int i = 1;i <= m;i++)
  {
    cin >> a[i].from >> a[i].to >> a[i].cost;
    
    g[a[i].from].pb(mp(a[i].to, a[i].cost));
    g[a[i].to].pb(mp(a[i].from, a[i].cost));

    C[a[i].from][a[i].to]++;
    C[a[i].to][a[i].from]++;
  }

  dfs();
  for (int i = 1;i <= n;i++)
    if (!c[i])
      dfs(i, i);
  for (int i = 1;i <= n;i++) g[i].clear(), p[i] = 0;

  for (int i = 1;i <= m;i++)
  {
    if (c[a[i].from] != c[a[i].to])
    {
      g[c[a[i].from]].pb(mp(c[a[i].to], a[i].cost));
      g[c[a[i].to]].pb(mp(c[a[i].from], a[i].cost));
    }
  }

  p[1] = 0;
  go();

  cin >> q;
  for (int it = 0;it < q;it++)
  {
    cin >> b[it].from >> b[it].to;

    int u, v; 
    u = b[it].from;
    v = b[it].to;
    if (c[u] == c[v]) continue;
    
    u = c[u];
    v = c[v];
    
    s[u]++;
    e[v]++;
    int p = lca(u, v);
    t[p]++;
  }

  calc();
  cout << ans << endl;
  return 0;
}

Second solution

import java.io.*;
import java.util.*;

public class AugClashNickAndJosephLand {

    int N, M;
    ArrayList<Integer> adj[];
    int u[], v[], w[];
    boolean vis[];
    int disc[], low[], componentId[], parent[];
    int time, total;
    int parentVertex[], parentFine[], depth[];
    int P[][];
    ArrayList<Integer> bridgeTree[];
    int pos[], neg[];
    long ans;
    
    AugClashNickAndJosephLand() throws IOException {
        solve();
    }

    public static void main(String args[]) {
        new Thread(null, new Runnable() {
            public void run() {
                try {
                    new AugClashNickAndJosephLand();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }, "1", 1 << 26).start();
    }

    @SuppressWarnings("unchecked")
    public void solve() {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        N = in.nextInt();
        M = in.nextInt();
        check(1, N, (int) 5e5);
        check(1, M, (int) 5e5);

        adj = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++)
            adj[i] = new ArrayList<Integer>();

        u = new int[M + 1];
        v = new int[M + 1];
        w = new int[M + 1];

        for (int i = 1; i <= M; i++) {
            u[i] = in.nextInt();
            v[i] = in.nextInt();
            w[i] = in.nextInt();
            check(1, u[i], N);
            check(1, v[i], N);
            check(1, w[i], (int) 1e6);
            adj[u[i]].add(i);
            adj[v[i]].add(i);
        }

        vis = new boolean[N + 1];
        disc = new int[N + 1];
        low = new int[N + 1];
        parent = new int[N + 1];
        time = 0;
        dfs(1);

        for (int i = 1; i <= N; i++) {
            check(vis[i]);
        }

        Arrays.fill(vis, false);
        total = 1;
        componentId = new int[N + 1];
        parentVertex = new int[N + 1];
        parentFine = new int[N + 1];
        depth = new int[N + 1];
        bridgeTree = new ArrayList[N + 1];
        bridgeTree[1] = new ArrayList<Integer>();
        dfs2(1, total);

        preprocess();

        int Q = in.nextInt();
        check(1, Q, (int) 5e5);

        pos = new int[total + 1];
        neg = new int[total + 1];
        ans = 0;

        while (Q-- > 0) {
            int a = in.nextInt();
            int b = in.nextInt();
            check(1, a, N);
            check(1, b, N);
            a = componentId[a];
            b = componentId[b];
            int lca = getLCA(a, b);
            pos[a]++;
            pos[lca]--;
            neg[b]++;
            neg[lca]--;
        }

        dfs3(1);

        out.println(ans);
        out.close();
    }

    public void dfs3(int curr) {
        for (int child : bridgeTree[curr]) {
            dfs3(child);
            pos[curr] += pos[child];
            neg[curr] += neg[child];
        }
        ans += Math.min(pos[curr], neg[curr]) * 1L * parentFine[curr];
    }

    public void dfs(int curr) {
        disc[curr] = low[curr] = time++;
        vis[curr] = true;
        for (int edge : adj[curr]) {
            int next = u[edge] + v[edge] - curr;
            if (vis[next]) {
                if (edge != parent[curr])
                    low[curr] = Math.min(low[curr], disc[next]);
            } else {
                parent[next] = edge;
                dfs(next);
                low[curr] = Math.min(low[next], low[curr]);
            }
        }
    }

    public void dfs2(int curr, int type) {
        componentId[curr] = type;
        vis[curr] = true;
        for (int edge : adj[curr]) {
            int next = u[edge] + v[edge] - curr;
            if (!vis[next]) {
                if (low[next] > disc[curr]) {
                    total++;
                    parentVertex[total] = type;
                    parentFine[total] = w[edge];
                    depth[total] = depth[type] + 1;
                    bridgeTree[type].add(total);
                    bridgeTree[total] = new ArrayList<Integer>();
                    dfs2(next, total);
                } else
                    dfs2(next, type);
            }
        }
    }

    public void preprocess() {

        P = new int[20][total + 1];

        for (int j = 0; (1 << j) < total; j++) {
            for (int i = 1; i <= total; i++) {
                P[j][i] = -1;
            }
        }

        for (int i = 1; i <= total; i++)
            P[0][i] = parentVertex[i];

        for (int j = 1; (1 << j) < total; ++j) {
            for (int i = 1; i <= total; ++i) {
                if (P[j - 1][i] != -1) {
                    P[j][i] = P[j - 1][P[j - 1][i]];
                }
            }
        }

    }

    public int getLCA(int p, int q) {

        if (depth[p] < depth[q]) {
            int tmp = p;
            p = q;
            q = tmp;
        }

        int log;
        for (log = 1; 1 << log <= depth[p]; log++)
            ;
        log--;

        for (int i = log; i >= 0; i--) {
            if (depth[p] - (1 << i) >= depth[q])
                p = P[i][p];
        }

        if (p == q)
            return p;

        for (int i = log; i >= 0; i--) {
            if (P[i][p] != -1 && P[i][p] != P[i][q]) {
                p = P[i][p];
                q = P[i][q];
            }
        }

        return parentVertex[p];
    }

    public void check(int low, int key, int high) {
        check(key >= low && key <= high);
    }

    public void check(boolean condition) {
        if (!condition)
            throw new RuntimeException();
    }

    static class InputReader {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int snext() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
        
        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}