Submission #1443823

---

Source Code Expand

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <string>
#include <cmath>
#include <set>
#include <functional>
#include <map>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cassert>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define show(x) cout << #x << " = " << x << endl;
typedef long long ll;
typedef pair<int,int> pii;
struct edge{
    int to;
    int w;
};
vector<edge>G[200001];
bool used[200001];
ll min_r,min_c;
ll cost[200001];
void dfs(int s){
    used[s] = true;
    rep(i,G[s].size()){
        if(!used[G[s][i].to]){
            cost[G[s][i].to] = G[s][i].w - cost[s];
            if(G[s][i].to >100000){
                min_c = min(min_c,cost[G[s][i].to]);
            }else{
                min_r = min(min_r,cost[G[s][i].to]);
            }
            dfs(G[s][i].to);
        }else{
            if(cost[G[s][i].to] != G[s][i].w - cost[s]){
                cout << "NO" << endl;
                exit(0);
            }
        }
    }
}
int main(){
    int h,w;
    cin >> h >> w;
    int n;
    cin >> n;
    vector<int> r(n),c(n),a(n);
    rep(i,100001){
        cost[i] = 1LL<<60;
        cost[i] *=-1;
    }
    rep(i,n){
        cin >> r[i] >> c[i] >> a[i];
        c[i] += 100000;
        G[r[i]].push_back(edge{c[i],a[i]});
        G[c[i]].push_back(edge{r[i],a[i]});
    }
    rep(i,n){
        if(!used[r[i]]){
            min_r = min_c = 1LL<<60;
            dfs(r[i]);
            if(min_r + min_c < 0){
                cout <<"NO" << endl;
                return 0;
            }
        }
    }
    cout << "YES" << endl;
}

Submission Info

Judge Result