HackerEarth Benny and Some Magic problem solution

In this HackerEarth Benny and Some Magic problem solution Benny appeared in a Magic labyrinth. Labyrinth consists of rooms and doors. Doors are unidirectional, they can be used only in one direction. There are even doors from the room to itself. When passing through the door, the master of the labyrinth gives Benny a coin.

Benny can move through the doors as much as she wants. But the only goal of the game is to get the score as high as possible. If Benny doesn’t use any door, her score is 0. Let the maximum value of coin earned by Benny is p and minimum value of coin earned by Benny is q, then the score is p – q. Help Benny to learn, what is the maximum score she can achieve.

HackerEarth Benny and Some Magic problem solution.

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("input.txt");
ofstream cout("output.txt");


struct Edge {
  int to, w;
};

vector < vector <Edge> > vv, vv_rev;


vector <bool> used;

vector <int> top_s, color;

void top_sort(int v) {
  used[v] = true;
  for (auto i : vv[v]) {
    int to = i.to;
    if (!used[to]) top_sort(to);
  }
  top_s.push_back(v);
}


void paint(int v, int col) {
  color[v] = col;
  for (auto i : vv_rev[v]) {
    int to = i.to;
    if (color[to] == -1) paint(to, col);
  }
}

const int INF = 1e9;

struct Edge2 {
  int to, minn, maxx;
};

vector < vector <Edge2> > edges;



int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  //cin >> n >> m;
  vv.resize(n + 1);
  vv_rev.resize(n + 1);
  used.resize(n + 1, false);
  color.resize(n + 1, -1);
  for (int i = 0; i < m; i++) {
    int f, t, w;
    scanf("%d%d%d", &f, &t, &w);
    //cin >> f >> t >> w;
    vv[f].push_back({ t, w });
    vv_rev[t].push_back({ f, w });
  }
  int col_now = 1;
  for (int i = 1; i <= n; i++) {
    if (!used[i]) {
      top_sort(i);
    }
  }
  reverse(top_s.begin(), top_s.end());
  for (auto i : top_s) {
    if (color[i] == -1) {
      paint(i, col_now++);
    }
  }
  vector < pair <int, int > > cost(col_now, { INF, -INF });
  for (int i = 1; i <= n; i++) {
    for (auto j : vv[i]) {
      if (color[j.to] == color[i]) {
        cost[color[i]].first = min(cost[color[i]].first, j.w);
        cost[color[i]].second = max(cost[color[i]].second, j.w);
      }
    }
  }
  edges.resize(col_now);
  for (int i = 1; i <= n; i++) {
    for (auto j : vv[i]) {
      if (color[j.to] != color[i]) {
        int from = color[i];
        int to = color[j.to];
        int min_w = min(j.w, cost[from].first);
        int max_w = max(j.w, cost[from].second);
        edges[from].push_back({ to, min_w, max_w });
      }
    }
  }
  vector <int> f_min(col_now, INF), g_min(col_now, INF), f_max(col_now, -INF), g_max(col_now, -INF);
  for (int i = 1; i < col_now; i++) {
    g_min[i] = f_min[i] = cost[i].first;
    g_max[i] = f_max[i] = cost[i].second;
  }
  for (int i = 1; i < col_now; i++) {
    for (auto j : edges[i]) {
      int to = j.to;
      f_min[to] = min(f_min[to], j.minn);
      f_min[to] = min(f_min[to], f_min[i]);
      f_max[to] = max(f_max[to], j.maxx);
      f_max[to] = max(f_max[to], f_max[i]);
    }
  }
  for (int i = col_now - 1; i > 0; i--) {
    for (auto j : edges[i]) {
      int to = j.to;
      g_min[i] = min(g_min[i], j.minn);
      g_min[i] = min(g_min[i], g_min[to]);
      g_max[i] = max(g_max[i], j.maxx);
      g_max[i] = max(g_max[i], g_max[to]);
    }
  }
  int ans = 0;
  for (int i = 1; i < col_now; i++) {
    ans = max(ans, f_max[i] - g_min[i]);
    ans = max(ans, g_max[i] - f_min[i]);
  }
  //cout << ans << 'n';
  printf("%dn", ans);
  return 0;
}

Second solution

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct edge {
  int from, to, w;
};

int const N = 333333;

int const INF = 1 << 30;

edge edges[N];
vector<int> g[N];
int was[N], val[N], mx[N], mn[N];

void dfs(int v, int w) {
  if (was[v]) return;
  val[v] = w;
  was[v] = 1;
  for (int to : g[v]) {
    dfs(to, w);
  }
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int from, to, w;
    scanf("%d%d%d", &from, &to, &w);
    --from;
    --to;
    edges[i] = {from, to, w};
    g[from].push_back(to);
  }
  std::sort(edges, edges + m, [](edge const &a, edge const &b) {
    return a.w < b.w;
  });
  for (int i = 0; i < n; i++) was[i] = false, val[i] = INF;
  for (int i = 0; i < m; i++) {
    dfs(edges[i].to, edges[i].w);
  }
  for (int i = 0; i < n; i++) mn[i] = val[i];
  for (int i = 0; i < n; i++) was[i] = false, val[i] = -INF;
  for (int i = m - 1; i >= 0; i--) {
    dfs(edges[i].to, edges[i].w);
  }
  for (int i = 0; i < n; i++) mx[i] = val[i];
  int ans = 0;
  for (int i = 0; i < m; i++) {
    int v = edges[i].from;
    if (mn[v] != INF) {
      ans = std::max(ans, edges[i].w - mn[v]);
    }
    if (mx[v] != -INF) {
      ans = std::max(ans, mx[v] - edges[i].w);
    }
  }
  printf("%dn", ans);
}

HackerEarth Benny and Some Magic problem solution

HackerEarth Benny and Some Magic problem solution.

Second solution

Leave a Reply

Pages

Practice