Guest User

Untitled

a guest
Sep 24th, 2016
263
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(x) (x).begin(), (x).end()
  4. #define li long long
  5. #define itn int
  6.  
  7. using namespace std;
  8.  
  9. inline int nxt(){
  10.     int n;
  11.     scanf("%d", &n);
  12.     return n;
  13. }
  14.  
  15. void panic() {
  16.     puts("No");
  17.     exit(0);
  18. }
  19.  
  20. int main(){
  21.  
  22.     int r = nxt(), c = nxt();
  23.     int n = nxt();
  24.     vector<vector<pair<int, int>>> R(r), C(c);
  25.     vector<pair<int, int>> cells;
  26.     for (int i = 0; i < n; i++) {
  27.         int x = nxt() - 1, y = nxt() - 1, v = nxt();
  28.         // R[x][y] = C[y][x] = v;
  29.         R[x].push_back({y, v});
  30.         C[y].push_back({x, v});
  31.         cells.push_back({x, y});
  32.     }
  33.  
  34.     for (int i = 0; i < r; i++) {
  35.         sort(all(R[i]));
  36.     }
  37.     for (int i = 0; i < c; i++) {
  38.         sort(all(C[i]));
  39.     }
  40.  
  41.     vector<int> vals;
  42.     for (int i = 0; i < r; i++) {
  43.         for (auto p : R[i]) {
  44.             vals.push_back(p.second);
  45.         }
  46.     }
  47.  
  48.     vector<vector<int>> ind_r(r), ind_c(c);
  49.     sort(all(cells));
  50.     int cur = 0;
  51.     for (int i = 0; i < r; i++) {
  52.         for (const auto& p : R[i]) {
  53.             ind_r[i].push_back(cur++);
  54.         }
  55.     }
  56.  
  57.     for (itn i = 0; i < c; i++) {
  58.         for (const auto& p : C[i]) {
  59.             ind_c[i].push_back(lower_bound(all(cells), make_pair(p.first, i)) - cells.begin());
  60.         }
  61.     }
  62.  
  63.     vector<char> used(n);
  64.  
  65.     vector<long long> add_r(r, 0), add_c(c, 0);
  66.     vector<char> set_r(r), set_c(c);
  67.  
  68.     for (int i = 0; i < n; i++) {
  69.         if (!used[i]) {
  70.             vector<int> st(1, i);
  71.             used[i] = 1;
  72.             add_r[cells[i].first] = 0;
  73.             add_c[cells[i].second] = vals[i];
  74.             set_r[cells[i].first] = set_c[cells[i].second] = 1;
  75.             long long min_r = 0, min_c = add_c[cells[i].second];
  76.             long long max_r = min_r, max_c = min_c;
  77.             while (!st.empty()) {
  78.                 int x = cells[st.back()].first;
  79.                 int y = cells[st.back()].second;
  80.                 st.pop_back();
  81.                 for (int j = 0; j < (int)R[x].size(); j++) {
  82.                     // if (it->first == y) {
  83.                     //  continue;
  84.                     // }
  85.                     int index = ind_r[x][j];
  86.                     if (used[index]) {
  87.                         continue;
  88.                     } else {
  89.                         if (set_c[R[x][j].first]) {
  90.                             if (add_r[x] + add_c[R[x][j].first] != R[x][j].second) {
  91.                                 panic();
  92.                             }
  93.                         } else {
  94.                             set_c[R[x][j].first] = 1;
  95.                             add_c[R[x][j].first] = R[x][j].second - add_r[x];
  96.                             min_c = min(min_c, add_c[R[x][j].first]);
  97.                             max_c = max(max_c, add_c[R[x][j].first]);
  98.                         }
  99.                         st.push_back(index);
  100.                         used[index] = 1;
  101.                     }
  102.                 }
  103.                 for (int j = 0; j < (int)C[y].size(); j++) {
  104.                     // if (it->first == y) {
  105.                     //  continue;
  106.                     // }
  107.                     int index = ind_c[y][j];
  108.                     if (used[index]) {
  109.                         continue;
  110.                     } else {
  111.                         if (set_r[C[y][j].first]) {
  112.                             if (add_r[C[y][j].first] + add_c[y] != C[y][j].second) {
  113.                                 panic();
  114.                             }
  115.                         } else {
  116.                             set_r[C[y][j].first] = 1;
  117.                             add_r[C[y][j].first] = C[y][j].second - add_c[y];
  118.                             min_r = min(min_r, add_r[C[y][j].first]);
  119.                             max_r = max(max_r, add_r[C[y][j].first]);
  120.                         }
  121.                         st.push_back(index);
  122.                         used[index] = 1;
  123.                     }
  124.                 }
  125.             }
  126.             if (min_c + min_r < 0) {
  127.                 panic();
  128.             }
  129.         }
  130.     }
  131.  
  132.     puts("Yes");
  133.  
  134.     return 0;
  135. }
Add Comment
Please, Sign In to add comment