Submission #1135408


Source Code Expand

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

#define int long long
#define INF (1LL<<60)
#define _1 first
#define _2 second
typedef pair<int, int> P;

int R, C, N;
vector<P> G[100000], B[100000];
int T[100000], M[100000];
vector<int> X;

bool g(int x) {
  X.push_back(x);
  for (auto &p : B[x]) {
    int u = p._1, v = T[x] + p._2;
    if (T[u] != INF && T[u] != v) return false;
    if (T[u] == INF) {
      T[u] = v;
      if (!g(u)) return false;
    }
  }
  return true;
}

bool f() {
  for (int y=0; y<R; y++) {
    sort(G[y].begin(), G[y].end());
    for (int i=1; i<G[y].size(); i++) {
      P &a = G[y][i-1], &b = G[y][i];
      B[a._1].push_back(P(b._1, b._2-a._2));
      B[b._1].push_back(P(a._1, a._2-b._2));
    }
  }
  for (int x=0; x<C; x++) T[x] = INF;
  for (int y=0; y<R; y++) {
    for (auto &p : G[y]) {
      int x = p._1;
      if (T[x] == INF) {
        X.clear();
        T[x] = 0;
        if (!g(x)) return false;
        int ma = INF, mb = INF;
        for (auto x : X) {
          mb = min(mb, T[x]);
          ma = min(ma, M[x] - T[x]);
        }
        if (ma+mb < 0) return false;
      }
    }
  }
  return true;
}

signed main() {
  cin >> R >> C >> N;
  for (int i=0; i<C; i++) M[i] = INF;
  for (int i=0; i<N; i++) {
    int r, c, a;
    cin >> r >> c >> a;
    r--, c--;
    G[r].push_back(P(c, a));
    M[c] = min(M[c], a);
  }
  if (f()) cout << "Yes\n";
  else cout << "No\n";
  return 0;
}

Submission Info

Submission Time
Task D - Grid and Integers
User funcsr
Language C++14 (GCC 5.4.1)
Score 800
Code Size 1538 Byte
Status AC
Exec Time 131 ms
Memory 14456 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 3 ms 4992 KB
0_01.txt AC 3 ms 4992 KB
0_02.txt AC 3 ms 4992 KB
0_03.txt AC 2 ms 4992 KB
0_04.txt AC 2 ms 4992 KB
1_00.txt AC 3 ms 6528 KB
1_01.txt AC 3 ms 6528 KB
1_02.txt AC 3 ms 6528 KB
1_03.txt AC 3 ms 6528 KB
1_04.txt AC 4 ms 6528 KB
1_05.txt AC 3 ms 6528 KB
1_06.txt AC 88 ms 9600 KB
1_07.txt AC 115 ms 9600 KB
1_08.txt AC 98 ms 11136 KB
1_09.txt AC 91 ms 11136 KB
1_10.txt AC 131 ms 11648 KB
1_11.txt AC 121 ms 11648 KB
1_12.txt AC 123 ms 14456 KB
1_13.txt AC 124 ms 14456 KB
1_14.txt AC 124 ms 14456 KB
1_15.txt AC 131 ms 14456 KB
1_16.txt AC 101 ms 13820 KB
1_17.txt AC 109 ms 14456 KB
1_18.txt AC 108 ms 14072 KB
1_19.txt AC 109 ms 14200 KB
1_20.txt AC 76 ms 10364 KB
1_21.txt AC 33 ms 6912 KB
1_22.txt AC 7 ms 5120 KB
1_23.txt AC 71 ms 8960 KB
1_24.txt AC 93 ms 11648 KB
1_25.txt AC 72 ms 9600 KB
1_26.txt AC 9 ms 5376 KB
1_27.txt AC 15 ms 6784 KB
1_28.txt AC 115 ms 11136 KB
1_29.txt AC 37 ms 7040 KB
1_30.txt AC 108 ms 12544 KB
1_31.txt AC 43 ms 7936 KB
1_32.txt AC 94 ms 11776 KB
1_33.txt AC 110 ms 12416 KB
1_34.txt AC 15 ms 6272 KB
1_35.txt AC 97 ms 10496 KB
1_36.txt AC 17 ms 5632 KB
1_37.txt AC 46 ms 7808 KB
1_38.txt AC 83 ms 9600 KB
1_39.txt AC 26 ms 6784 KB
1_40.txt AC 80 ms 8576 KB
1_41.txt AC 39 ms 7552 KB
1_42.txt AC 99 ms 12028 KB
1_43.txt AC 72 ms 8576 KB
1_44.txt AC 91 ms 9088 KB
1_45.txt AC 31 ms 7808 KB
1_46.txt AC 106 ms 11776 KB
1_47.txt AC 40 ms 9216 KB
1_48.txt AC 34 ms 6784 KB
1_49.txt AC 13 ms 5888 KB
1_50.txt AC 60 ms 7936 KB
1_51.txt AC 107 ms 11520 KB
1_52.txt AC 10 ms 6528 KB
1_53.txt AC 18 ms 6784 KB
1_54.txt AC 33 ms 6400 KB
1_55.txt AC 47 ms 6912 KB
1_56.txt AC 72 ms 8448 KB
1_57.txt AC 115 ms 12672 KB
1_58.txt AC 92 ms 9984 KB
1_59.txt AC 8 ms 6016 KB
1_60.txt AC 3 ms 4992 KB
1_61.txt AC 3 ms 4992 KB
1_62.txt AC 3 ms 4992 KB
1_63.txt AC 3 ms 4992 KB