Incorrect C++ Solution for the "Optimal Playlist" problem from Yandex.Algorithm 2015 Qualification Round

optimal_playlist.cpp

/*
ID: aydn.yu1
LANG: C++11
TASK: 
*/
 
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cctype>
#include <iomanip>
#include <bitset>
#include <list>
#include <deque>
#include <utility>
#include <functional>
#include <cassert>
#include <complex>
#include <valarray>
 
using namespace std;
 
#define all(a)              (a).begin(), (a).end()
#define ms(a, b)            memset(a, b, sizeof(a))
#define mc(a, b)            memcpy(a, b, sizeof(b))
#define mp                  make_pair
#define mt                  make_tuple
#define pb                  push_back
#define eb                  emplace_back
#define fore(it, a)         for (auto it = (a).begin(), it##_ = (a).end(); it != it##_; ++it)
#define f0r(i, a)           for (int i = 0, i##_ = (a); i < i##_; ++i)
#define read(type, args...) type args; rdr,args;
#define fi                  first
#define se                  second
#define bit_no              __builtin_popcount
#define left(a)             (2*(a))
#define right(a)            (2*(a)+1)
#define mid(left, right)    (((left)+(right))/2)
#define PI                  acos(-1)
#define X                   fi
#define Y                   se
#define sq(a)               ((a)*(a))
 
#ifdef EBUG
    #define debug(args...)      do {cerr << #args << ": "; dbg,args; cerr << endl;} while(0)
#else
    #define debug(args...)
#endif
 
typedef long long               ll;
typedef long double             ld;
typedef unsigned long long      ull;
typedef vector<int>             vi;
typedef vector<vi>              vvi;
typedef pair<int, int>          ii;
typedef tuple<int, int, int>    iii;
typedef vector<ii>              vii;
typedef vector<iii>             viii;
 
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
 
template<typename T>
using max_pq = priority_queue<T>;
 
const int inf = 2e9+5;
const ll l_inf = 2e18+5;
const int mod_v = 1e9+7;
const int max_n = 1e5+5;
 
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
 
#define UP      0
#define RIGHT   1
#define DOWN    2
#define LEFT    3
 
template<typename T>
T gcd(T a, T b)
{
    while (b) {
        T temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}
 
template<typename T>
tuple<T, T, T> egcd(T a, T b)
{
    T x1 = 1, x2 = 0, y1 = 0, y2 = 1;
    while (b) {
        T q = a / b, r = a % b;
        T new_x = x1 - q*x2, new_y = y1 - q*y2;
        x1 = x2, y1 = y2, x2 = new_x, y2 = new_y;
        a = b, b = r;
    }
    return make_tuple(a, x1, y1);
}
 
inline ll lcm(ll a, ll b)
{
    return a*b/gcd(a, b);
}
 
template<typename T>
inline T mod(T a, T b = mod_v)
{
    return (a % b + b) % b;
}
 
template<typename T>
inline T mod_inv(T a, T b = mod_v)
{
    return mod(get<1>(egcd(a, b)), b);
}
 
template<typename T>
inline T sum(T a, T b, T m = mod_v)
{
    return mod(mod(a, m) + mod(b, m), m);
}
 
template<typename T>
inline T difference(T a, T b, T m = mod_v)
{
    return mod(mod(a, m) - mod(b, m), m);
}
 
inline ll product(ll a, ll b, ll m = mod_v)
{
    return mod(mod(a, m) *  mod(b, m), m);
}
 
inline ll quotient(ll a, ll b, ll m = mod_v)
{
    return mod(mod(a, m) * mod_inv(b, m), m);
}
 
template<typename T,typename T2>
ostream& operator<< (ostream &s, const pair<T,T2> &p) {return s << p.fi << ' ' << p.se << ' ';}
 
template<typename T,typename T2>
istream& operator>> (istream &s, pair<T,T2> &p) {return s >> p.fi >> p.se;}
 
template<typename T>
ostream& operator<< (ostream &s, const vector<T> &v)  {for (auto it: v) s << it << ' '; return s;}
 
template<typename T>
istream& operator>> (istream &s, vector<T> &v) {fore (it, v) s >> *it; return s;}
 
template<typename T>
void read_range(T beg, T end)
{
    while (beg != end)
        cin >> *beg++;
}
 
template<typename T>
void print_range(T beg, T end)
{
    while (beg != end)
        cout << *beg++ << ' ';
}
 
struct reader
{
    template<typename T>
    reader& operator, (T &v)
    {
        cin >> v;
        return *this;
    }
} rdr;
 
struct debugger
{
    template<typename T>
    debugger& operator, (const T &v)
    {
        cerr << v << ", ";
        return *this;
    }
} dbg;
 
/***************************************************************
----------------------------------------------------------------
----------------------------------------------------------------
***************************************************************/
 
vii adj[max_n];
vi adj2[max_n];
int md, dfs_low[max_n], dfs_num[max_n], scc_no[max_n], tm_cnt, scc_cnt, n, m, in_degree[max_n];
bool in_st[max_n];
stack<int> st;
 
void tarjan(int u)
{
    dfs_num[u] = dfs_low[u] = ++tm_cnt;
    in_st[u] = true;
    st.push(u);
    for (auto &a: adj[u]) {
        int v = a.fi, w = a.se;
        if (w > md)
            continue;
        if (dfs_num[v] == 0)
            tarjan(v);
        if (in_st[v])
            dfs_low[u] = min(dfs_low[u], dfs_low[v]);
    }
    if (dfs_low[u] == dfs_num[u]) {
        int cur;
        ++scc_cnt;
        do {
            cur = st.top();
            st.pop();
            in_st[cur] = false;
            scc_no[cur] = scc_cnt;
        } while (u != cur);
    }
}
 
bool f()
{
    ms(dfs_low, 0);
    ms(dfs_num, 0);
    ms(scc_no, 0);
    ms(in_degree, 0);
    scc_cnt = tm_cnt = 0;
 
    for (int i = 1; i <= n; ++i)
        if (dfs_num[i] == 0)
            tarjan(i);
    
    for (int u = 1; u <= n; ++u)
        for (auto &a: adj[u]) {
            int v = a.fi, w = a.se;
            if (w > md or scc_no[u] == scc_no[v])
                continue;
            adj2[scc_no[u]].pb(scc_no[v]);
            ++in_degree[scc_no[v]];
        }
    
    int u = -1;
    for (int i = 1; i <= scc_cnt; ++i)
        if (in_degree[i] == 0 and u == -1)
            u = i;
        else if (in_degree[i] == 0)
            return false;
 
    while (true) {
        if (adj2[u].empty())
            return true;
        int new_u = -1;
        for (int v: adj2[u]) {
            --in_degree[v];
            if (in_degree[v] == 0 and new_u == -1)
                new_u = v;
            else if (in_degree[v] == 0)
                return false;
        }
        u = new_u;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    
    cin >> n >> m;
    f0r (i, m) {
        read(int, u, v, w);
        adj[u].eb(v, w);
    }
    
    int lo = 1, hi = 1e9;
    for (md = mid(lo, hi); lo < hi; md = mid(lo, hi))
        if (f())
            hi = md;
        else
            lo = md+1;
 
    cout << (f() ? lo : -1);
    
    return 0;
}