HackerEarth Childfree Time problem solution

In this HackerEarth Childfree Time problem solution The weekend is coming soon and you want to spend some time without worrying about your younger son Tommy. He is 6 years old and likes playing computer games a lot. Knowing that, you have written a special computer game for him.

The game is about exploring labyrinths. You have prepared big dungeons to keep him busy for a long time. More specifically, the dungeons consists of R rooms and P portals between them. The rooms are numbered from 1 to R. The portals are one directional and each of them have assigned a time needed to teleport Tommy from one room to another. In order to prevent Tommy from being scared of losing himself in the dungeons, you designed them in such a way that if a player is in a room A, then there is no possibility to use a sequence of portals from A which will teleport him again to A. In order to make Tommy happy, you created some number of rooms without any outgoing portal. Each such room contains a treasure and the game ends as soon as Tommy is teleported to such a room. For any other room, he will take some time to explore it, and you know that the maximum time that he can spend exploring a single room is 2 time units.

Tommy can start the game in any room he wants and you are interested in the maximum number of time units he can spend exploring the dungeons until he finds any treasure.

HackerEarth Childfree Time problem solution.

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream> 
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
#define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));
#define DBG cerr << "debug here" << endl;
#define DBGV(vari) cerr << #vari<< " = "<< (vari) <<endl;

typedef long long ll;

const int MAXN = 1e6;
const int MAXM = 1e6;
const int MAXC = 1e9;
const int MAXT = 2;

ll dp[MAXN];
vi g[MAXN];
vector<pii> pred[MAXN];

vi top_order;
bool visited[MAXN];

void dfs_top(int v)
{
    visited[v] = 1;
    FOR(i, g[v].size())
    {
        int u = g[v][i];
        if(visited[u]) continue;
        dfs_top(u);
    }
    top_order.pb(v);
}

int main()    
{
    int n, m;
    scanf("%d %d", &n, &m);
    assert(n <= MAXN);
    assert(m <= MAXM);
    FOR(i, m)
    {
        int v, u, t;
        scanf("%d %d %d", &v, &u, &t);
        assert(1 <= v && v <= n);
        assert(1 <= u && u <= n);
        assert(1 <= t && t <= MAXC);
        --v; --u; 
        g[v].pb(u);
        pred[u].pb(mp(v, t));
    }
    FOR(i, n)
    {
        if(!visited[i]) dfs_top(i);
    } 
    reverse(ALL(top_order));
    ll res = 0;
    FOR(i, n)
    {
        int v = top_order[i];
        FOR(j, pred[v].size())
        {
            int u = pred[v][j].fi;
            int t = pred[v][j].se;
            ll c = dp[u] + MAXT + t;
            if(dp[v] == -1 || dp[v] < c)
            {
                dp[v] = c;
            }
        }
        REMAX(res, dp[v]);
    }
    printf("%lld\n", res);

    return 0;
}

Second solution

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int>   II;
typedef vector< II >      VII;
typedef vector<int>     VI;
typedef vector< VI >  VVI;
typedef long long int   LL;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(),a.end()
#define SET(a,b) memset(a,b,sizeof(a))

#define si(n) scanf("%d",&n)
#define dout(n) printf("%d\n",n)
#define sll(n) scanf("%lld",&n)
#define lldout(n) printf("%lld\n",n)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);
const int N = int(1e6)+1;
const int M = int(1e6)+1;
const int C = int(1e9)+1;
VII g[N];
int indeg[N];
LL dp[N];
int main()
{
  int n,m;
  si(n);si(m);
  assert(n<N && m<M);
  for(int i=0;i<m;i++)
  {
    int u,v,w;
    si(u);si(v);si(w);
    assert(1<=u && u<=n);
    assert(1<=v && v<=n);
    assert(1<=w && w<=C);
    g[v].PB(MP(u,w));
    indeg[u]++;
  }
  queue<int> Q;
  for(int i=1;i<=n;i++)
    if(!indeg[i])
    {
      Q.push(i);
      dp[i]=0;
    }
  while(!Q.empty())
  {
    int u=Q.front();
    Q.pop();
    for(int i=0;i<SZ(g[u]);i++)
    {
      int w = g[u][i].F;
      dp[w] = max(dp[w],dp[u]+g[u][i].S+2);
      indeg[w]--;
      if(!indeg[w])
        Q.push(w);
    }
  }
  LL ans = 0;
  for(int i=1;i<=n;i++)
    ans = max(ans,dp[i]);
  lldout(ans);
  return 0;
}