Submission #1175919

---

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;

vector<vvi> g;
vll offset;

void dfs(int u) {
  for (vi v_d : g[u]) {
    ll s = offset[u] + v_d[1];
    if (offset[v_d[0]] == INF) {
      offset[v_d[0]] = s;
      dfs(v_d[0]);
    } else if (offset[v_d[0]] != s) {
      printf("No\n");
      exit(0);
    }
  }
}

int main() {
  int r, c;
  scanf("%d%d", &r, &c);
  g.resize(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]));
  }
  rep (i, r) {
    FOR (j, 1, (int)ca[i].size()) {
      g[ca[i][0][0]].push_back((vi){ca[i][j][0], ca[i][j][1] - ca[i][0][1]});
      g[ca[i][j][0]].push_back((vi){ca[i][0][0], ca[i][0][1] - ca[i][j][1]});
    }
  }

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

  offset.assign(c, INF);
  rep (i, c) {
    if (uf.size(i) == 1) continue;
    if (offset[i] == INF) {
      offset[i] = 0;
      dfs(i);
    }
  }

  vi roots;
  vi root_minc(c, c+10);
  rep (i, c) {
    if (uf.size(i) == 1) continue;
    roots.push_back(uf.root(i));
  }
  sort(all(roots));
  roots.erase(unique(all(roots)), roots.end());
  for (int root : roots) {
    int x = root;
    root_minc[root] = x;
    for (/*x = uf.root(x)*/; x != -1; x = uf.get_next(x)) {
      if (offset[root_minc[root]] > offset[x]) {
        root_minc[root] = x;
      }
    }
  }

  rep (i, r) {
    if (ca[i].size() <= 1) continue;
    int min_c = root_minc[uf.root(ca[i][0][0])];
    //if (min_c == c+10) continue;
    if (ca[i][0][1] + offset[min_c] - offset[ca[i][0][0]] < 0) {
      debug(i);
      printf("No\n");
      return 0;
    }
  }

  printf("Yes\n");

  return 0;
}

Submission Info

Judge Result