Submission #65469990

---

Source Code Expand

#ifdef LOCAL
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using ull = unsigned long long;
using ld = long double;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second

#ifdef LOCAL
#define ZTMYACANESOCUTE // freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 6;
#endif

void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow (ll x, ll exp, ll mod = LLONG_MAX) { if (x == 0) return 0; ll res = 1; while (exp > 0) { if (exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1; } return res; }

void solve() {
    int n, m; cin >> n >> m;
    n++;
    vector<vector<pll>> adj(n);
    rep (i, 0, m) {
        int l, r, s; cin >> l >> r >> s;
        l--;
        adj[l].pb({r, s});
        adj[r].pb({l, -s});
    }
    rep (i, 1, n) adj[i].pb({i - 1, -1});
    vector<ll> dis(n, LINF), cnt(n, 0);
    auto SPFA = [&](int st, ll d) -> bool {
        vector<bool> vis(n, 0);
        queue<int> q;
        vis[st] = 0;
        dis[st] = d;
        q.push(st);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for (auto [v, w] : adj[u]) {
                if (chmin(dis[v], dis[u] + w)) {
                    cnt[v]++;
                    if (cnt[v] == n) {
                        return false;
                    }
                    if (!vis[v]) {
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
        }
        return true;
    };
    ll l = 0, r = 1e14 + 5;
    if (!SPFA(n - 1, r)) {
        cout << -1 << '\n';
        return;
    }
    while (r - l > 1) {
        ll mid = l + r >> 1;
        fill(all(dis), LINF);
        fill(all(cnt), 0);
        if (SPFA(n - 1, mid) && dis[0] >= 0) r = mid;
        else l = mid;
    }
    cout << r << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:99:20: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   99 |         ll mid = l + r >> 1;
      |                  ~~^~~

Judge Result