HackerEarth Sightseeing Walk problem solution

In this HackerEarth Sightseeing Walk problem solution Kevin wants to have a spectacular hiking tour over the mountains.

Now he needs to plan his route. Kevin knows N sightseeing points. Height of the i-th point equals Hi. Also there are M lanes connecting these points. These lanes are designed in such a way that using the i-th lane Kevin can walk from point ai to point bi. Note that he can’t walk in the opposite direction using this lane but may walk using some other lane.

Kevin thinks that the path is the most spectacular if the height difference of his route is the largest. So he needs to choose start and finish points such that it is possible to reach finish from start and Hfinish – Hstart is maximized.

Your task is to help him and tell him the maximum possible Hfinish – Hstart .

HackerEarth Sightseeing Walk problem solution.

#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <cassert>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
#include <complex>
using namespace std;

#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
#define FILL(A,value) memset(A,value,sizeof(A))

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979
#define x0 ikjnrmthklmnt
#define y0 lkrjhkltr
#define y1 ewrgrg

typedef long long Int;
typedef unsigned long long UInt;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<Int, Int> PLL;
typedef pair<double, double> PDD;
typedef complex<double> base;

const int INF = 1000000000;
const int BASE = 1000000007;
const int MAX = 100007;
const int MAX2 = 7777;
const int MAXE = 100000;
const int ADD = 1000000;
const int MOD = 1000000007;
const int CNT = 800;

VI G[MAX];
int H[MAX];

int res;
bool U[MAX];

void dfs(int v, int sh)
{
    res = max(res , H[v] - sh);
    U[v] = 1;
    FOR(i,0,SZ(G[v]))
    {
        int to = G[v][i];
        if (U[to]) continue;
        dfs(to, sh);
    }
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("distance.in",  "r", stdin);
    //freopen("distance.out", "w", stdout);
    //freopen("out.txt" , "w" , stdout);
    
    int t;
    cin >> t;
    FOR(tt,0,t)
    {
        int n , m;
        cin >> n >> m;
        FOR(i,0,n)
        {
            G[i].clear();
            U[i] = 0;
        }
        res = 0;
        
        FOR(i,0,n)
        {
            scanf("%d" , &H[i]);
        }
        
        FOR(i,0,m)
        {
            int a , b;
            scanf("%d%d" , &a , &b);
            --a; --b;
            G[a].push_back(b);
        }
        vector<PII> A;
        FOR(i,0,n)
        {
            A.push_back(MP(H[i] , i));
        }
        sort(ALL(A));
        
        FOR(i,0,n)
        {
            int v = A[i].second;
            if (U[v]) continue;
            dfs(v , A[i].first);
        }
        
        
        cout << res << endl;
    }
    
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector <int> G[MAXN];
bool vis[MAXN];
int ans, ht[MAXN];
void dfs(int pos, int start)
{
  vis[pos] = true;
  ans = max(ans, ht[pos] - ht[start]);
  for (int i = 0; i < G[pos].size(); ++i)
  {
    if(!vis[G[pos][i]])
      dfs(G[pos][i],start);
  }
}
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
    int n,m;
    cin>>n>>m;
    vector < pair<int,int> > A;
    for (int i = 1; i <= n; ++i)
    {
      cin>>ht[i];
      A.push_back(make_pair(ht[i],i));
    }
    for (int i = 0; i < m; ++i)
    {
      int a,b;
      cin>>a>>b;
      G[a].push_back(b);
    }
    sort(A.begin(), A.end());
    ans = 0;
    for (int i = 0; i < A.size(); ++i)
    {
      int pos = A[i].second;
      if(!vis[pos])
        dfs(pos,pos);
    }
    cout<<ans<<"n";
    // cleanup
    memset(vis, false, sizeof vis);
    for (int i = 1; i <= n; ++i)
    {
      G[i].clear();
    }
  }
  return 0;
}