Submission #2123017

---

Source Code Expand

#include <iostream>
#include <utility>
#include <algorithm>
#define llint long long
#define inf ((llint)1e18)

using namespace std;

llint R, C, N;
pair< pair<llint, llint>, llint > RC[100005], CR[100005];

llint row_parent[100005], row_dif[100005];
llint col_parent[100005], col_dif[100005];
llint min_row[100005], min_col[100005];

llint root(llint parent[], llint dif[], int i)
{
	if(parent[i] == i) return i;
	
	root(parent, dif, parent[i]);
	dif[i] = dif[parent[i]] + dif[i];
	return parent[i] = parent[parent[i]];
}

bool same(llint parent[], llint dif[], int i, int j)
{
	return root(parent, dif, i) == root(parent, dif, j);
}

void unite(llint parent[], llint dif[], int i, int j, llint val)
{
	int root_i = root(parent, dif, i), root_j = root(parent, dif, j);
	if(root_i == root_j) return;
	
	llint x = dif[j] - val - dif[i];
	parent[root_i] = root_j;
	dif[root_i] = x;
}

int main(void)
{
	cin >> R >> C >> N;
	llint r, c, a;
	for(int i = 0; i < N; i++){
		cin >> r >> c >> a;
		RC[i] = make_pair(make_pair(r, c), a);
		CR[i] = make_pair(make_pair(c, r), a);
	}
	sort(RC, RC + N);
	sort(CR, CR + N);
	
	for(int i = 1; i <= R; i++) row_parent[i] = i;
	for(int i = 1; i <= C; i++) col_parent[i] = i;
	
	int prev = -1;
	for(int i = 0; i < N; i++){
		if(RC[i].first.first == prev){
			int pc = RC[i-1].first.second, cc = RC[i].first.second;
			if(same(col_parent, col_dif, pc, cc)){
				if(col_dif[cc] - col_dif[pc] != RC[i].second - RC[i-1].second){
					cout << "No" << endl;
					return 0;
				}
			}
			unite(col_parent, col_dif, pc, cc, RC[i].second - RC[i-1].second);
		}
		prev = RC[i].first.first;
	}
	prev = -1;
	for(int i = 0; i < N; i++){
		if(CR[i].first.first == prev){
			int pr = CR[i-1].first.second, cr = CR[i].first.second;
			if(same(row_parent, row_dif, pr, cr)){
				if(row_dif[cr] - row_dif[pr] != CR[i].second - CR[i-1].second){
					cout << "No" << endl;
					return 0;
				}
			}
			unite(row_parent, row_dif, pr, cr, CR[i].second - CR[i-1].second);
		}
		prev = CR[i].first.first;
	}
	
	for(int i = 1; i <= R; i++) min_row[i] = inf;
	for(int i = 1; i <= R; i++){
		root(row_parent, row_dif, i);
		min_row[row_parent[i]] = min(min_row[row_parent[i]], row_dif[i]);
	}
	for(int i = 1; i <= C; i++) min_col[i] = inf;
	for(int i = 1; i <= C; i++){
		root(col_parent, col_dif, i);
		min_col[col_parent[i]] = min(min_col[col_parent[i]], col_dif[i]);
	}
	
	for(int i = 0; i < N; i++){
		if(RC[i].second - row_dif[RC[i].first.first] + min_row[row_parent[RC[i].first.first]] - col_dif[RC[i].first.second] + min_col[row_parent[RC[i].first.second]] < 0){
			cout << "No" << endl;
			return 0;
		}
	}
	
	cout << "Yes" << endl;
	return 0;
}

Submission Info

Judge Result