Submission #1258719

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int DIM = 2e5 + 5;

bitset<DIM> oki; int val[DIM];
vector<pair<int, int>> edg[DIM];

void dfs( int x, bool &ok ) {
    oki[x] = true;
    
    for( pair<int, int> y : edg[x] ) {
        if( oki[y.first] == true )
            ok &= ( val[x] + val[y.first] == y.second );
        else {
            val[y.first] = y.second - val[x];
            dfs( y.first, ok );
        }
    }
    
    return;
}

int main( void ) {
    
    int r, c, n;
    cin >> r >> c >> n;
    
    for( int i = 1; i <= n; i ++ ) {
        int x, y, z;
        cin >> x >> y >> z;
        
        edg[x].push_back( make_pair( r + y, z ) );
        edg[r + y].push_back( make_pair( x, z ) );
    }
    
    bool ok = true;
    for( int i = 1; i <= r + c; i ++ ) {
        if( oki[i] == false )
            dfs( i, ok );
    }
    
    ok &= ( *min_element( val + 1, val + r + 1 ) +
            *min_element( val + r + 1, val + r + c + 1 ) >= 0 );
    
    cout << ( ( ok == true ) ? "Yes" : "No" ) << endl;
    return 0;
}

Submission Info

Judge Result