Submission #1175894


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);
  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) {
        if (uf.same(ca[i][j][0], ca[i][j+1][0])) {
          printf("No\n");
          return 0;
        } else {
          int x = ca[i][j+1][0];
          ll offset_adjust = s - offset[x];
          for (x = uf.root(x); x != -1; x = uf.get_next(x)) {
            offset[x] += offset_adjust;
          }
        }
      }
      uf.unite(ca[i][j][0], ca[i][j+1][0]);
    }
  }

  unordered_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

Submission Time
Task D - Grid and Integers
User tspcx
Language C++14 (Clang 3.8.0)
Score 800
Code Size 3486 Byte
Status AC
Exec Time 1817 ms
Memory 20256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 5
AC × 69
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt
Case Name Status Exec Time Memory
0_00.txt AC 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
0_03.txt AC 1 ms 256 KB
0_04.txt AC 1 ms 256 KB
1_00.txt AC 5 ms 4608 KB
1_01.txt AC 4 ms 4608 KB
1_02.txt AC 5 ms 4608 KB
1_03.txt AC 5 ms 4608 KB
1_04.txt AC 5 ms 4608 KB
1_05.txt AC 4 ms 4608 KB
1_06.txt AC 76 ms 20256 KB
1_07.txt AC 71 ms 20256 KB
1_08.txt AC 73 ms 17716 KB
1_09.txt AC 71 ms 17716 KB
1_10.txt AC 75 ms 17280 KB
1_11.txt AC 61 ms 16256 KB
1_12.txt AC 77 ms 16256 KB
1_13.txt AC 63 ms 16256 KB
1_14.txt AC 72 ms 16256 KB
1_15.txt AC 70 ms 16256 KB
1_16.txt AC 68 ms 16256 KB
1_17.txt AC 73 ms 16256 KB
1_18.txt AC 72 ms 16256 KB
1_19.txt AC 71 ms 16256 KB
1_20.txt AC 727 ms 9088 KB
1_21.txt AC 22 ms 6272 KB
1_22.txt AC 5 ms 2304 KB
1_23.txt AC 48 ms 11648 KB
1_24.txt AC 1092 ms 11008 KB
1_25.txt AC 591 ms 9216 KB
1_26.txt AC 5 ms 1536 KB
1_27.txt AC 10 ms 4096 KB
1_28.txt AC 957 ms 14720 KB
1_29.txt AC 25 ms 6912 KB
1_30.txt AC 1817 ms 14208 KB
1_31.txt AC 30 ms 9088 KB
1_32.txt AC 181 ms 11008 KB
1_33.txt AC 1705 ms 14336 KB
1_34.txt AC 11 ms 3712 KB
1_35.txt AC 56 ms 12800 KB
1_36.txt AC 12 ms 4352 KB
1_37.txt AC 103 ms 5632 KB
1_38.txt AC 56 ms 12800 KB
1_39.txt AC 18 ms 6272 KB
1_40.txt AC 53 ms 12288 KB
1_41.txt AC 27 ms 8832 KB
1_42.txt AC 87 ms 11648 KB
1_43.txt AC 46 ms 11520 KB
1_44.txt AC 73 ms 12672 KB
1_45.txt AC 43 ms 4736 KB
1_46.txt AC 1067 ms 13952 KB
1_47.txt AC 264 ms 5888 KB
1_48.txt AC 26 ms 4864 KB
1_49.txt AC 9 ms 3328 KB
1_50.txt AC 99 ms 8576 KB
1_51.txt AC 609 ms 12928 KB
1_52.txt AC 8 ms 4352 KB
1_53.txt AC 13 ms 5120 KB
1_54.txt AC 22 ms 6144 KB
1_55.txt AC 24 ms 6272 KB
1_56.txt AC 148 ms 10368 KB
1_57.txt AC 1513 ms 13568 KB
1_58.txt AC 470 ms 12416 KB
1_59.txt AC 6 ms 3328 KB
1_60.txt AC 1 ms 256 KB
1_61.txt AC 1 ms 256 KB
1_62.txt AC 1 ms 256 KB
1_63.txt AC 1 ms 256 KB