Submission #7138931


Source Code Expand

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);
 
using namespace std;
 
namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;
 
struct uf{
	vi p;
	vector<ll> h;
	vector<vi> s;
	uf(int n){
		p.resize(n);
		h.resize(n);
		s.resize(n);
		rep(i, n){
			p[i] = i;
			s[i].pb(i);
		}
	}
	int root(int x){
		assert(x >= 0 && x < p.size());
		return x == p[x] ? x : (p[x] = root(p[x]));
	}
	bool merge(int A, int B, ll b_minus_a){
		int a = root(A), b = root(B);
		if(a == b){
			return h[B] - h[A] == b_minus_a;
		}
		if(s[a].size() < s[b].size()){
			swap(a, b);
			b_minus_a *= -1;
		}
		p[b] = a;
		
		ll d = h[A] - h[B] + b_minus_a;
		for(int i : s[b]){
			s[a].pb(i);
			h[i] += d;
		}
		s[b].erase(all(s[b]));
		return 1;
	}
};
bool check(const vector<vector<pi>> &es, int n){
	uf u = uf(n);
	
	for(const auto &v : es) for(const pi &p : v){
		assert(0 <= p.first && p.first < n);
	}
	
	for(const auto &v : es) if(v.size() > 1){
		rep(j, v.size() - 1){
			pi a = v[j], b = v[j + 1];
			if(!u.merge(a.first, b.first, b.second - a.second)) return 0;
		}
	}
	map<int,ll> mnR;
	for(const auto &v : es) for(const pi &p : v){
		int pos = p.first, val = p.second, r = u.root(pos);
		
		assert(u.h[r] == 0);
		
		ll mn = mnR.count(r) ? mnR[r] : 1e18;
		mnR[r] = mn = min(mn, val - u.h[pos]);
	}
	//dbg(mnR);
	for(const auto &v : es) for(const pi &p : v){
		int pos = p.first, val = p.second, r = u.root(pos);
		//dbg(r, mnR[r], u.h[pos], val);
		if(mnR[r] + u.h[pos] < 0) return 0;
	}
	return 1;
}
int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	
	int h, w, n; cin >> h >> w >> n;
	vector<vector<pi>> tate(w), yoko(h);
	rep(i, n){
		int y, x, a; cin >> y >> x >> a; y--; x--;
		yoko[y].emplace_back(x, a);
		tate[x].emplace_back(y, a);
	}
	cout << (check(tate, h) && check(yoko, w) ? "Yes" : "No") << endl;
	
	return 0;
}

Submission Info

Submission Time
Task D - Grid and Integers
User nadeko
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3249 Byte
Status WA
Exec Time 233 ms
Memory 24128 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 5
AC × 50
WA × 19
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 18 ms 11648 KB
1_01.txt AC 18 ms 11648 KB
1_02.txt AC 18 ms 11648 KB
1_03.txt AC 11 ms 11648 KB
1_04.txt AC 18 ms 11648 KB
1_05.txt AC 11 ms 11648 KB
1_06.txt AC 225 ms 24128 KB
1_07.txt AC 233 ms 24128 KB
1_08.txt AC 185 ms 17856 KB
1_09.txt AC 103 ms 17792 KB
1_10.txt AC 173 ms 16320 KB
1_11.txt AC 57 ms 14720 KB
1_12.txt AC 93 ms 16640 KB
1_13.txt AC 65 ms 16640 KB
1_14.txt AC 94 ms 16640 KB
1_15.txt AC 67 ms 16512 KB
1_16.txt AC 90 ms 16612 KB
1_17.txt AC 67 ms 16640 KB
1_18.txt AC 66 ms 16512 KB
1_19.txt AC 65 ms 16512 KB
1_20.txt AC 29 ms 4864 KB
1_21.txt WA 27 ms 7424 KB
1_22.txt WA 9 ms 6272 KB
1_23.txt WA 58 ms 12800 KB
1_24.txt AC 36 ms 5760 KB
1_25.txt AC 31 ms 6400 KB
1_26.txt WA 6 ms 1920 KB
1_27.txt WA 13 ms 5248 KB
1_28.txt AC 52 ms 12032 KB
1_29.txt WA 31 ms 8960 KB
1_30.txt AC 47 ms 9856 KB
1_31.txt WA 38 ms 12288 KB
1_32.txt AC 35 ms 4096 KB
1_33.txt AC 47 ms 9984 KB
1_34.txt WA 13 ms 4992 KB
1_35.txt WA 36 ms 5760 KB
1_36.txt WA 18 ms 8704 KB
1_37.txt AC 19 ms 3712 KB
1_38.txt WA 64 ms 12800 KB
1_39.txt WA 24 ms 9856 KB
1_40.txt WA 42 ms 13312 KB
1_41.txt WA 36 ms 14080 KB
1_42.txt AC 37 ms 5248 KB
1_43.txt AC 59 ms 13440 KB
1_44.txt AC 43 ms 12416 KB
1_45.txt AC 11 ms 2944 KB
1_46.txt AC 47 ms 10496 KB
1_47.txt WA 14 ms 3712 KB
1_48.txt AC 17 ms 4480 KB
1_49.txt WA 12 ms 5376 KB
1_50.txt AC 30 ms 8832 KB
1_51.txt AC 46 ms 8064 KB
1_52.txt AC 22 ms 10548 KB
1_53.txt WA 17 ms 7936 KB
1_54.txt WA 29 ms 9344 KB
1_55.txt WA 21 ms 5888 KB
1_56.txt AC 37 ms 10880 KB
1_57.txt AC 45 ms 7424 KB
1_58.txt AC 44 ms 11264 KB
1_59.txt AC 16 ms 7440 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