Submission #1258727

---

Source Code Expand

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

const int DIM = 2e5 + 5;

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

void dfs( int x, int r, bool &ok, long long &mn1, long long &mn2 ) {
    oki[x] = true;
    
    if( x <= r )
        mn1 = min( mn1, val[x] );
    else
        mn2 = min( mn2, val[x] );
    
    for( pair<int, long long> 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, r, ok, mn1, mn2 );
        }
    }
    
    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 ) {
            long long mn1 = numeric_limits<long long> :: max();
            long long mn2 = numeric_limits<long long> :: max();
           
            dfs( i, r, ok, mn1, mn2 );
            ok &= ( mn1 + mn2 >= 0 );
        }
    }
    
    
    cout << ( ( ok == true ) ? "Yes" : "No" ) << endl;
    return 0;
}

Submission Info

Judge Result