Submission #895509

---

Source Code Expand

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

vector<vector<pair<int,int>>> rows;
vector<vector<pair<int,int>>> cols;
map<pair<int,int>, int> rdiff;
map<pair<int,int>, int> cdiff;

int main() {
  int R,C;
  int N;
  cin >> R >> C >> N;
  rows = vector<vector<pair<int,int> >>(R);
  cols = vector<vector<pair<int,int> >>(C);
  for(int i = 0; i < N; i++) {
    int r, c, a;
    cin >> r >> c >> a;
    r--;c--;
    rows[r].emplace_back(c, a);
    cols[c].emplace_back(r, a);
  }
  // check rows
  bool ok = true;
  for(int sw = 0; sw < 2; sw++) {
    vector<int> minc(cols.size());
    vector<pair<pair<int,int>,int>> diffs;
    rdiff.clear();
    for(int i = 0; i < cols.size(); i++) {
      if(cols[i].size() > 0) {
        minc[i] = cols[i][0].second;
        for(size_t j = 1; j < cols[i].size(); j++) {
          minc[i] = min(minc[i], cols[i][j].second);
        }
      }
    }
    for(int i = 0; i < rows.size(); i++) {
      sort(rows[i].begin(), rows[i].end());
      for(int j = 0; j < (int)rows[i].size() - 1; j++) {
        int diff = rows[i][j+1].second - rows[i][j].second;
        auto p = make_pair(rows[i][j].first, rows[i][j+1].first);
        diffs.push_back(make_pair(make_pair(rows[i][j+1].first, rows[i][j].first), diff));
        if(rdiff.count(p)) {
          if(rdiff[p] != diff) ok = false;
        }else {
          rdiff[p] = diff;
        }
        if(diff < -minc[rows[i][j].first]) ok = false;
        if(-diff < -minc[rows[i][j + 1].first]) ok = false;
      }
    }
    // 推移率の確認
    sort(diffs.begin(), diffs.end());
    vector<long> p(cols.size(), 0);
    vector<bool> u(cols.size(), false);
    for(auto t: diffs) {
      int start = t.first.second;
      int end = t.first.first;
      int diff = t.second;
      if(!u[start] && !u[end]) {
        u[start] = u[end] = true;
        p[start] = 0; p[end] = diff;
      }else if(u[start] && u[end]) {
        if(p[end] - p[start] != diff) ok = false;
      }else if(u[start] && !u[end]) {
        u[end] = true;
        p[end] = p[start] + diff;
      }else {
        p[start] = p[end] - diff;
        u[start] = true;
      }
    }
    swap(rows, cols);
  }
  if(ok) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Submission Info

Judge Result