Submission #2090594

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
using p = pair<lli, lli>;
vector<p> e[100005];
vector<p> ee[100005];
bool usd[100005] = {};
lli wei1[200005] = {};
lli wei2[200005] = {};

bool visited[300005] = {};
lli inf = 1e18;
lli mi1 = inf, mi2 = inf;

void get(int u, int ty)
{
    int idx = u + ty * 100003;
    if (visited[idx]) {
        return;
    }
    visited[idx] = true;
    if (ty == 0) {
        mi1 = min(mi1, wei1[u]);
        for (auto s : e[u]) {
            get(s.first, 1);
        }
    } else {
        mi2 = min(mi2, wei2[u]);
        for (auto s : ee[u]) {
            get(s.first, 0);
        }
    }
}
void dfs(int u)
{
    for (auto s : e[u]) {
        if (usd[s.first]) {
            wei1[u] = s.second - wei2[s.first];
        }
    }
    for (auto s : e[u]) {
        usd[s.first] = true;
        wei2[s.first] = s.second - wei1[u];
    }
}
int main()
{
    int r, c, n;
    cin >> r >> c >> n;
    vector<lli> u(n), v(n), a(n);
    rep(i, n)
    {
        cin >> u[i] >> v[i] >> a[i];
        u[i]--, v[i]--;
        e[u[i]].push_back(p(v[i], a[i]));
        ee[v[i]].push_back(p(u[i], a[i]));
    }
    rep(i, r) dfs(i);
    rep(i, n)
    {
        if (wei1[u[i]] + wei2[v[i]] != a[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    bool flag = true;
    rep(i, r)
    {
        mi1 = inf, mi2 = inf;
        get(i, 0);
        if (mi1 + mi2 < 0)
            flag = false;
    }
    cout << (flag ? "Yes" : "No") << endl;
}

Submission Info

Judge Result