Submission #1698367


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const LL INF = 1e15;

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int H, W, N;
  cin >> H >> W >> N;
  vector<vector<PLL>> G(H+W);
  REP(i,N){
	int y, x, a;
	cin >> y >> x >> a;
	--x;
	--y;
	G[y].EB(H+x, a);
	G[H+x].EB(y, a);
  }

  VL dist(H+W, INF);
  function<bool(int,LL&,LL&)> dfs = [&](int u, LL& mx, LL& my){
	if(u < H) mini(my, dist[u]);
	else mini(mx, dist[u]);
	
	for(auto& e: G[u]){
	  if(dist[e.FF] == INF){
		dist[e.FF] = e.SS - dist[u];
		if(!dfs(e.FF, mx, my)) return false;
	  }
	  else{
		if(dist[e.FF] + dist[u] != e.SS)
		  return false;
	  }
	}
	return true;
  };
  
  REP(i,H+W){
	if(dist[i] != INF) continue;
	dist[i] = 0;
	LL mx = INF, my = INF;
	if(!dfs(i, mx, my) || mx+my < 0){
	  cout << "No" << endl;
	  return 0;
	}
  }
  cout << "Yes" << endl;

  return 0;
}

Submission Info

Submission Time
Task D - Grid and Integers
User okaduki
Language C++14 (GCC 5.4.1)
Score 800
Code Size 1982 Byte
Status AC
Exec Time 79 ms
Memory 21120 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 6528 KB
1_01.txt AC 5 ms 6528 KB
1_02.txt AC 5 ms 6528 KB
1_03.txt AC 4 ms 6528 KB
1_04.txt AC 5 ms 6528 KB
1_05.txt AC 3 ms 6528 KB
1_06.txt AC 48 ms 12800 KB
1_07.txt AC 54 ms 12800 KB
1_08.txt AC 61 ms 12032 KB
1_09.txt AC 46 ms 11904 KB
1_10.txt AC 63 ms 11776 KB
1_11.txt AC 53 ms 11776 KB
1_12.txt AC 67 ms 21120 KB
1_13.txt AC 61 ms 21120 KB
1_14.txt AC 64 ms 21120 KB
1_15.txt AC 65 ms 21120 KB
1_16.txt AC 71 ms 17664 KB
1_17.txt AC 67 ms 20736 KB
1_18.txt AC 79 ms 19584 KB
1_19.txt AC 73 ms 19840 KB
1_20.txt AC 33 ms 6912 KB
1_21.txt AC 18 ms 4736 KB
1_22.txt AC 4 ms 2560 KB
1_23.txt AC 33 ms 8448 KB
1_24.txt AC 40 ms 8448 KB
1_25.txt AC 32 ms 6912 KB
1_26.txt AC 4 ms 1280 KB
1_27.txt AC 8 ms 4224 KB
1_28.txt AC 55 ms 11136 KB
1_29.txt AC 19 ms 5376 KB
1_30.txt AC 49 ms 10496 KB
1_31.txt AC 21 ms 7680 KB
1_32.txt AC 40 ms 7552 KB
1_33.txt AC 50 ms 10496 KB
1_34.txt AC 8 ms 3584 KB
1_35.txt AC 38 ms 5632 KB
1_36.txt AC 10 ms 3968 KB
1_37.txt AC 20 ms 4480 KB
1_38.txt AC 37 ms 8960 KB
1_39.txt AC 14 ms 5632 KB
1_40.txt AC 45 ms 8448 KB
1_41.txt AC 21 ms 7808 KB
1_42.txt AC 40 ms 7168 KB
1_43.txt AC 32 ms 8064 KB
1_44.txt AC 40 ms 8832 KB
1_45.txt AC 12 ms 3968 KB
1_46.txt AC 47 ms 10112 KB
1_47.txt AC 17 ms 4864 KB
1_48.txt AC 14 ms 3456 KB
1_49.txt AC 7 ms 3200 KB
1_50.txt AC 28 ms 6272 KB
1_51.txt AC 50 ms 10112 KB
1_52.txt AC 7 ms 5248 KB
1_53.txt AC 11 ms 5248 KB
1_54.txt AC 18 ms 4736 KB
1_55.txt AC 20 ms 4096 KB
1_56.txt AC 34 ms 7680 KB
1_57.txt AC 51 ms 9600 KB
1_58.txt AC 43 ms 9216 KB
1_59.txt AC 6 ms 3968 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