Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define all(x) (x).begin(), (x).end()
- #define li long long
- #define itn int
- using namespace std;
- inline int nxt(){
- int n;
- scanf("%d", &n);
- return n;
- }
- void panic() {
- puts("No");
- exit(0);
- }
- int main(){
- int r = nxt(), c = nxt();
- int n = nxt();
- vector<vector<pair<int, int>>> R(r), C(c);
- vector<pair<int, int>> cells;
- for (int i = 0; i < n; i++) {
- int x = nxt() - 1, y = nxt() - 1, v = nxt();
- // R[x][y] = C[y][x] = v;
- R[x].push_back({y, v});
- C[y].push_back({x, v});
- cells.push_back({x, y});
- }
- for (int i = 0; i < r; i++) {
- sort(all(R[i]));
- }
- for (int i = 0; i < c; i++) {
- sort(all(C[i]));
- }
- vector<int> vals;
- for (int i = 0; i < r; i++) {
- for (auto p : R[i]) {
- vals.push_back(p.second);
- }
- }
- vector<vector<int>> ind_r(r), ind_c(c);
- sort(all(cells));
- int cur = 0;
- for (int i = 0; i < r; i++) {
- for (const auto& p : R[i]) {
- ind_r[i].push_back(cur++);
- }
- }
- for (itn i = 0; i < c; i++) {
- for (const auto& p : C[i]) {
- ind_c[i].push_back(lower_bound(all(cells), make_pair(p.first, i)) - cells.begin());
- }
- }
- vector<char> used(n);
- vector<long long> add_r(r, 0), add_c(c, 0);
- vector<char> set_r(r), set_c(c);
- for (int i = 0; i < n; i++) {
- if (!used[i]) {
- vector<int> st(1, i);
- used[i] = 1;
- add_r[cells[i].first] = 0;
- add_c[cells[i].second] = vals[i];
- set_r[cells[i].first] = set_c[cells[i].second] = 1;
- long long min_r = 0, min_c = add_c[cells[i].second];
- long long max_r = min_r, max_c = min_c;
- while (!st.empty()) {
- int x = cells[st.back()].first;
- int y = cells[st.back()].second;
- st.pop_back();
- for (int j = 0; j < (int)R[x].size(); j++) {
- // if (it->first == y) {
- // continue;
- // }
- int index = ind_r[x][j];
- if (used[index]) {
- continue;
- } else {
- if (set_c[R[x][j].first]) {
- if (add_r[x] + add_c[R[x][j].first] != R[x][j].second) {
- panic();
- }
- } else {
- set_c[R[x][j].first] = 1;
- add_c[R[x][j].first] = R[x][j].second - add_r[x];
- min_c = min(min_c, add_c[R[x][j].first]);
- max_c = max(max_c, add_c[R[x][j].first]);
- }
- st.push_back(index);
- used[index] = 1;
- }
- }
- for (int j = 0; j < (int)C[y].size(); j++) {
- // if (it->first == y) {
- // continue;
- // }
- int index = ind_c[y][j];
- if (used[index]) {
- continue;
- } else {
- if (set_r[C[y][j].first]) {
- if (add_r[C[y][j].first] + add_c[y] != C[y][j].second) {
- panic();
- }
- } else {
- set_r[C[y][j].first] = 1;
- add_r[C[y][j].first] = C[y][j].second - add_c[y];
- min_r = min(min_r, add_r[C[y][j].first]);
- max_r = max(max_r, add_r[C[y][j].first]);
- }
- st.push_back(index);
- used[index] = 1;
- }
- }
- }
- if (min_c + min_r < 0) {
- panic();
- }
- }
- }
- puts("Yes");
- return 0;
- }
Add Comment
Please, Sign In to add comment