Submission #1135368

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define int long long
#define INF (1LL<<58)
#define _1 first
#define _2 second
typedef pair<int, int> P;

int R, C, N;
vector<P> G[100000], B[100000];
int T[100000];

bool g(int x) {
  for (auto &p : B[x]) {
    int u = p._1, v = T[x] + p._2;
    if (T[u] != INF && T[u] != v) return false;
    if (T[u] == INF) {
      T[u] = v;
      if (!g(u)) return false;
    }
  }
  return true;
}

bool f() {
  for (int y=0; y<R; y++) {
    sort(G[y].begin(), G[y].end());
    P &a = G[y][0];
    for (int i=1; i<G[y].size(); i++) {
      P &b = G[y][i];
      B[a._1].push_back(P(b._1, b._2-a._2));
      B[b._1].push_back(P(a._1, a._2-b._2));
    }
  }
  for (int x=0; x<C; x++) T[x] = INF;
  T[0] = 0;
  if (!g(0)) return false;
  for (int x=0; x<C; x++) {
    if (T[x] == INF) {
      //T[x] = (1LL<<30);
      //if (!g(x)) return false;
    }
  }
  int ma = INF, mb = INF;
  for (int x=0; x<C; x++) mb = min(mb, T[x]);
  for (int y=0; y<R; y++) {
    for (auto &p : G[y]) {
      if (T[p._1] == INF) continue;
      ma = min(ma, p._2 - T[p._1]);
    }
  }
  return ma+mb >= 0;
}

signed main() {
  cin >> R >> C >> N;
  for (int i=0; i<N; i++) {
    int r, c, a;
    cin >> r >> c >> a;
    r--, c--;
    G[r].push_back(P(c, a));
  }
  if (f()) cout << "Yes\n";
  else cout << "No\n";
  return 0;
}

Submission Info

Judge Result