Submission #896446

---

Source Code Expand

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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define has(c,i) ((c).find(i) != end(c))
#define DBGDO(X) ({ if(1) cerr << "DBGDO: " << (#X) << " = " << (X) << endl; })

ll m, n, k;
vl x, y, a;
vector<vector<pll>> adj;
ll C = 0;
vl comp, h;
bool ok = true;

void dfs(ll i, ll x) {
	comp[i] = C;
	h[i] = x;
	for (auto e: adj[i]) {
		if (comp[e.yy] == -1) dfs(e.yy,x + e.xx);
		else if (h[e.yy] != x + e.xx) ok = false;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> m >> n >> k;
	
	x.resize(k), y.resize(k), a.resize(k);
	FOR(i,0,k) cin >> x[i] >> y[i] >> a[i], x[i]--, y[i]--;

	adj.resize(m+n);
	FOR(i,0,k) adj[x[i]].eb(a[i],m+y[i]), adj[m+y[i]].eb(-a[i],x[i]);
	comp.resize(m+n,-1), h.resize(m+n,0);//, dx.resize(m+n), dy.resize(m+n);
	FOR(i,0,m+n) if (comp[i] == -1) dfs(i,0), C++;
	
	vl chx(C,oo), chy(C,oo);
	FOR(i,0,m) chx[comp[i]] = min(chx[comp[i]],-h[i]);
	FOR(i,m,m+n) chy[comp[i]] = min(chy[comp[i]],h[i]);
	
	FOR(c,0,C) if (chx[c] + chy[c] < 0) ok = false;

	cout << (ok ? "Yes" : "No") << endl;

}

Submission Info

Judge Result