Submission #2121257

---

Source Code Expand

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

const int N = 200005;
const long long INF = 1e18 + 123;

int R, C, n;
bool vis[N];
long long a[N];
vector < pair<int, int> > g[N];
vector <int> comp;

void dfs(int u) {
	vis[u] = 1;
	comp.push_back(u);
	for (auto e : g[u]) {
		int v = e.second, w = e.first;
		if (!vis[v]) a[v] = w - a[u], dfs(v);
		else if (vis[v] && a[v] != w - a[u]) { cout << "No\n"; exit(0); }
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> R >> C >> n;
	for (int i = 1; i <= n; ++i) {
		int x, y, w; cin >> x >> y >> w;
		g[x].push_back(make_pair(w, y + R));
		g[y + R].push_back(make_pair(w, x));
	}

	for (int i = 1; i <= R + C; ++i) if (!vis[i]) {
		comp.clear();
		dfs(i);
		long long mr = INF, mc = INF;
		for (int u : comp) {
			if (u <= R) {
				mr = min(mr, a[u]);
			} else {
				mc = min(mc, a[u]);
			}
		}
		if (mr + mc < 0) return cout << "No\n", 0;
	}

	cout << "Yes\n";
}

Submission Info

Judge Result