Submission #1609049

---

Source Code Expand

#include <bits/stdc++.h>

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define FORD(i,b,e) for(int i=(b); i >= (e); --i)
#define SIZE(c) (int) (c).size()
#define FORE(i,c) FOR(i,0,SIZE(c)-1)
#define FORDE(i,c) FORD(i,SIZE(c)-1,0)

#define pb push_back
#define mp make_pair
#define st first
#define nd second


using namespace std;

typedef long long ll;
typedef pair <int,int> pii;
typedef pair <ll,ll> pll;

typedef vector <int> VI;
typedef vector <bool> VB;
typedef vector <pii> VP;
typedef vector <ll> VL;
typedef vector <pll> VPL;

typedef vector <VI> VVI;
typedef vector <VL> VVL;
typedef vector <VB> VVB;
typedef vector <VP> VVP;

const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000000000000001LL;


/*************************************************************************/

int main() {
    ios_base::sync_with_stdio(0);
    
    int r, c, n;
    cin >> r >> c >> n;
    
    VVP g(r + c);
    
    FOR(_,1,n) {
        int x, y, val;
        cin >> x >> y >> val; x--; y--;
        
        g[x].pb({r + y, val});
        g[r + y].pb({x, val});
    }
    
    VL value(r + c, -1);
    VVI component;
    
    queue <int> q;
    
    FOR(i,0,r+c-1) if (value[i] == -1) {
        component.emplace_back();
    
        q.push(i);
        value[i] = 0;
        
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            
            component.back().pb(v);
            
            for (auto e : g[v]) {
                int u = e.st;
                int newValue = e.nd - value[v];
                
                if (value[u] != -1 && value[u] != newValue) {
                    cout << "No";
                    return 0;
                }
                
                if (value[u] == -1) {
                    value[u] = newValue;
                    q.push(u);
                }
            }
        }
    }
    
    for (auto &c : component) {
        ll minRow = LINF;
        ll minCol = LINF;
        
        for (int v : c) {
            if (v < r) {
                minRow = min(minRow, value[v]);
            } else {
                minCol = min(minCol, value[v]);
            }
        }
        
        if (minRow + minCol < 0) {
            cout << "No";
            return 0;
        }
    }
    
    cout << "Yes";

    return 0;
}

/*************************************************************************/

Submission Info

Judge Result