Submission #1175902

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef deque<bool> db;
template<class T> using vv=vector<vector< T > >;

class UF {
private:
  vector<int> data; // parent or size
  vector<int> next;
  vector<int> last;
  void init(int n) {
    data.assign(n, -1);
    next.assign(n, -1);
    last.resize(n);
    for (int i = 0; i < n; ++i) {
      last[i] = i;
    }
  }

public:
  UF() {}
  UF(int n) {
    init(n);
  }
  int root(int x) {
    if (data[x] < 0) return x;
    return data[x] = root(data[x]);
  }
  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    if (data[x] > data[y]) swap(x, y); // data[x] and data[y] are negative.
    data[x] += data[y];
    data[y] = x;
    next[last[x]] = y;
    last[x] = last[y];
    return true;
  }
  int size(int x) {
    return -data[root(x)];
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int get_next(int x) {
    return next[x];
  }
};

ll INF = 2e15;

int main() {
  int r, c;
  scanf("%d%d", &r, &c);
  int n;
  scanf("%d", &n);
  vvi rca(n, vi(3));
  vv<vi> ca(r);
  rep (i, n) {
    int ri, ci, ai;
    scanf("%d%d%d", &ri, &ci, &ai);
    ri -= 1;
    ci -= 1;
    ca[ri].push_back((vi){ci, ai});
  }
  rep (i, r) {
    sort(all(ca[i]));
  }

  UF uf(c);
  rep (i, r) {
    if (ca[i].size() == 0) continue;
    rep (j, (int)ca[i].size() - 1) {
      uf.unite(ca[i][j][0], ca[i][j+1][0]);
    }
  }

  vll offset(c, INF);
  rep (i, r) {
    if (ca[i].size() == 0) continue;
    if (offset[ca[i][0][0]] == INF) {
      offset[ca[i][0][0]] = 0;
    }
    rep (j, (int)ca[i].size() - 1) {
      ll s = offset[ca[i][j][0]] + ca[i][j+1][1] - ca[i][j][1];
      if (offset[ca[i][j+1][0]] == INF) {
        offset[ca[i][j+1][0]] = s;
      } else if (offset[ca[i][j+1][0]] != s) {
        printf("No\n");
        return 0;
      }
    }
  }

  map<int, int> roots;
  rep (i, c) {
    if (uf.size(i) == 1) continue;
    roots[uf.root(i)] = c + 10;
  }
  for (auto p = roots.begin(); p != roots.end(); ++p) {
    int x = p->first;
    p->second = x;
    for (; x != -1; x = uf.get_next(x)) {
      if (offset[p->second] > offset[x]) {
        p->second = x;
      }
    }
  }

  rep (i, r) {
    rep (j, (int)ca[i].size()) {
      int min_c = roots[uf.root(ca[i][j][0])];
      if (ca[i][j][1] + offset[min_c] - offset[ca[i][j][0]] < 0) {
        printf("No\n");
        return 0;
      }
    }
  }
  printf("Yes\n");

  return 0;
}

Submission Info

Judge Result