Submission #1698314


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;
  map<int,vector<PLL>> col, row;
  REP(i,N){
	int y, x, a;
	cin >> y >> x >> a;
	--x;
	--y;
	row[y].EB(x, a);
	col[x].EB(y, a);
  }

  vector<vector<PLL>> Gx(W), Gy(H);
  vector<LL> dx(W, INF), dy(H, INF);
  vector<LL> mx(W, INF), my(H, INF);
  REP(y,H){
	if(!row.count(y)) continue;
	vector<PLL>& xs = row[y];
	SORT(xs);
	for(int i=0;i+1<SZ(xs);++i){
	  Gx[xs[i].FF].EB(xs[i+1].FF, xs[i+1].SS - xs[i].SS);
	  Gx[xs[i+1].FF].EB(xs[i].FF, xs[i].SS - xs[i+1].SS);
	}
	REP(i,SZ(xs)) mini(mx[xs[i].FF], xs[i].SS);
  }
  REP(x,W){
	if(!col.count(x)) continue;
	vector<PLL>& ys = col[x];
	SORT(ys);
	for(int i=0;i+1<SZ(ys);++i){
	  Gy[ys[i].FF].EB(ys[i+1].FF, ys[i+1].SS - ys[i].SS);
	  Gy[ys[i+1].FF].EB(ys[i].FF, ys[i].SS - ys[i+1].SS);
	}
	REP(i,SZ(ys)) mini(my[ys[i].FF], ys[i].SS);
  }

  bool ng = false;
  function<bool(vector<vector<PLL>>&,int,VL&,VI&)> dfs = [&](vector<vector<PLL>>& G, int u, VL& d, VI& vis){
	vis.PB(u);
	for(auto& e: G[u]){
	  if(d[e.FF] == INF){
		d[e.FF] = d[u] + e.SS;
		if(!dfs(G, e.FF, d,vis))
		  return false;
	  }
	  else{
		if(d[u] + e.SS != d[e.FF]){
		  return false;
		}
	  }
	}
	return true;
  };

  REP(x,W){
	if(dx[x] != INF) continue;
	dx[x] = 0;
	VI vis;
	if(!dfs(Gx, x, dx, vis)){
	  ng = true;
	  break;
	}
	int mix = x;
	LL m = mx[x];
	for(int u: vis){
	  if(mx[u] + dx[u] < m){
		mix = u;
		m = mx[u] + dx[u];
	  }
	}
	if(m < 0){
	  for(int u: vis){
		if(dx[u] - m > mx[u]){
		  ng = true;
		  break;
		}
	  }
	}
  }
  REP(y,H){
	if(dy[y] != INF) continue;
	dy[y] = 0;
	VI vis;
	if(!dfs(Gy, y, dy, vis)){
	  ng = true;
	  break;
	}
	int mix = y;
	LL m = my[y];
	for(int u: vis){
	  if(my[u] + dy[u] < m){
		mix = u;
		m = my[u] + dy[u];
	  }
	}
	if(m < 0){
	  for(int u: vis){
		if(dy[u] - m > my[u]){
		  ng = true;
		  break;
		}
	  }
	}
  }

  //REP(x,W) cout << dx[x] << " "; cout << endl;
  //REP(y,H) cout << dy[y] << endl;
  cout << (ng? "No": "Yes") << endl;
  
  return 0;
}

Submission Info

Submission Time
Task D - Grid and Integers
User okaduki
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3290 Byte
Status WA
Exec Time 201 ms
Memory 31932 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 5
AC × 56
WA × 13
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 13 ms 8064 KB
1_01.txt AC 13 ms 8064 KB
1_02.txt AC 13 ms 8064 KB
1_03.txt AC 13 ms 8064 KB
1_04.txt AC 13 ms 8064 KB
1_05.txt AC 6 ms 8064 KB
1_06.txt AC 193 ms 29952 KB
1_07.txt AC 188 ms 29952 KB
1_08.txt AC 200 ms 27904 KB
1_09.txt AC 194 ms 27904 KB
1_10.txt AC 201 ms 26880 KB
1_11.txt AC 183 ms 26880 KB
1_12.txt AC 196 ms 31928 KB
1_13.txt AC 185 ms 31928 KB
1_14.txt AC 192 ms 31932 KB
1_15.txt AC 194 ms 31928 KB
1_16.txt AC 188 ms 30264 KB
1_17.txt AC 188 ms 31800 KB
1_18.txt AC 186 ms 31288 KB
1_19.txt AC 189 ms 31288 KB
1_20.txt WA 89 ms 14720 KB
1_21.txt AC 45 ms 9472 KB
1_22.txt AC 10 ms 3712 KB
1_23.txt AC 109 ms 18304 KB
1_24.txt WA 114 ms 17920 KB
1_25.txt WA 94 ms 15124 KB
1_26.txt AC 10 ms 2304 KB
1_27.txt AC 22 ms 6784 KB
1_28.txt WA 160 ms 24192 KB
1_29.txt AC 52 ms 10752 KB
1_30.txt WA 180 ms 23680 KB
1_31.txt AC 66 ms 14336 KB
1_32.txt WA 109 ms 16384 KB
1_33.txt WA 154 ms 23680 KB
1_34.txt AC 22 ms 5888 KB
1_35.txt AC 92 ms 18048 KB
1_36.txt AC 25 ms 6656 KB
1_37.txt WA 52 ms 9216 KB
1_38.txt AC 119 ms 19968 KB
1_39.txt AC 39 ms 9728 KB
1_40.txt AC 114 ms 19072 KB
1_41.txt AC 60 ms 14080 KB
1_42.txt AC 113 ms 17792 KB
1_43.txt WA 105 ms 17920 KB
1_44.txt WA 122 ms 20992 KB
1_45.txt AC 31 ms 8064 KB
1_46.txt WA 155 ms 23040 KB
1_47.txt AC 45 ms 10240 KB
1_48.txt WA 43 ms 7680 KB
1_49.txt AC 18 ms 5120 KB
1_50.txt WA 79 ms 13952 KB
1_51.txt AC 131 ms 20608 KB
1_52.txt AC 19 ms 7296 KB
1_53.txt AC 30 ms 8448 KB
1_54.txt AC 47 ms 9600 KB
1_55.txt AC 50 ms 10496 KB
1_56.txt AC 95 ms 17152 KB
1_57.txt AC 141 ms 21632 KB
1_58.txt AC 141 ms 20508 KB
1_59.txt AC 14 ms 5504 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