Submission #1231788


Source Code Expand

#include <iostream>
#include <climits>
#include <vector>
#include <cmath>
#include <map>

using namespace std;

void dfs(vector< vector< pair<int, int> > > &graph, vector<int> &val, int root) {

	for (int i = 0; i < graph[root].size(); ++i) {
		if (val[graph[root][i].first] == INT_MAX) {
			val[graph[root][i].first] = graph[root][i].second - val[root];
			dfs(graph, val, graph[root][i].first);
		}
	}

}

int find(int x, vector<int> &root) {

	if (root[x] == x) {
		return x;
	} else {
		root[x] = find(root[x], root);
		return root[x];
	}

}

void merge(int x, int y, vector<int> &root) {

	int u = find(x, root);
	int v = find(y, root);
	if (u != v) {
		root[v] = u;
	}

}

int main(void) {

	int R, C, N;
	cin >> R >> C >> N;

	vector<int> r(N), c(N), a(N);
	vector< vector< pair<int, int> > > graph(R + C);
	vector<int> val(R + C, INT_MAX);
	vector<int> component(R + C);
	map<int, pair<int, int> > table;
	map<int, pair<int, int> >::iterator iter;

	for (int i = 0; i < R + C; ++i) {
		component[i] = i;
	}

	for (int i = 0; i < N; ++i) {
		cin >> r[i] >> c[i] >> a[i];
		--r[i]; --c[i];
		graph[r[i]].push_back(make_pair(R + c[i], a[i]));
		graph[R + c[i]].push_back(make_pair(r[i], a[i]));
		merge(r[i], R + c[i], component);
	}

	for (int i = 0; i < graph.size(); ++i) {
		if (val[i] == INT_MAX && graph[i].size() > 0) {
			val[i] = 0;
			dfs(graph, val, i);
		}
	}

	/*
	for (int i = 0; i < val.size(); ++i) {
		cout << val[i] << " ";
	}
	cout << endl;
	*/

	for (int i = 0; i < N; ++i) {
		if (val[r[i]] != INT_MAX && val[R + c[i]] != INT_MAX) {
			if (val[r[i]] + val[R + c[i]] != a[i]) {
				cout << "No" << endl;
				return 0;
			}
		}
	}

	for (int i = 0; i < R + C; ++i) {
		if (val[i] != INT_MAX) {
			table[find(i, component)] = make_pair(INT_MAX, INT_MAX);
		}
		// cout << component[i] << " ";
	}
	// cout << endl;

	for (int i = 0; i < R; ++i) {
		if (val[i] != INT_MAX) {
			table[find(i, component)].first = min(table[find(i, component)].first, val[i]);
		}
	}
	for (int i = R; i < (R + C); ++i) {
		if (val[i] != INT_MAX) {
			table[find(i, component)].second = min(table[find(i, component)].second, val[i]);
		}
	}

	for (iter = table.begin(); iter != table.end(); ++iter) {
		if (iter->second.first != INT_MAX && iter->second.second != INT_MAX) {
			if (iter->second.first + iter->second.second < 0) {
				cout << "No" << endl;
				return 0;
			}
		}
	}

	cout << "Yes" << endl;
	return 0;

}

Submission Info

Submission Time
Task D - Grid and Integers
User indcn20171018
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2540 Byte
Status WA
Exec Time 291 ms
Memory 20224 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 5
AC × 66
WA × 3
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 4 ms 6528 KB
1_01.txt AC 4 ms 6528 KB
1_02.txt AC 4 ms 6528 KB
1_03.txt AC 4 ms 6528 KB
1_04.txt AC 4 ms 6528 KB
1_05.txt AC 4 ms 6528 KB
1_06.txt AC 259 ms 20224 KB
1_07.txt AC 291 ms 20224 KB
1_08.txt AC 169 ms 13952 KB
1_09.txt AC 164 ms 13952 KB
1_10.txt AC 170 ms 12416 KB
1_11.txt AC 125 ms 10752 KB
1_12.txt AC 137 ms 15488 KB
1_13.txt AC 129 ms 15488 KB
1_14.txt AC 138 ms 15488 KB
1_15.txt AC 136 ms 15488 KB
1_16.txt AC 109 ms 13824 KB
1_17.txt WA 122 ms 15232 KB
1_18.txt WA 122 ms 14720 KB
1_19.txt WA 123 ms 14848 KB
1_20.txt AC 80 ms 5760 KB
1_21.txt AC 52 ms 5760 KB
1_22.txt AC 9 ms 2816 KB
1_23.txt AC 112 ms 9984 KB
1_24.txt AC 100 ms 6912 KB
1_25.txt AC 83 ms 6272 KB
1_26.txt AC 11 ms 1408 KB
1_27.txt AC 22 ms 4864 KB
1_28.txt AC 136 ms 9856 KB
1_29.txt AC 60 ms 6400 KB
1_30.txt AC 131 ms 10112 KB
1_31.txt AC 71 ms 9216 KB
1_32.txt AC 97 ms 5760 KB
1_33.txt AC 132 ms 10112 KB
1_34.txt AC 23 ms 4096 KB
1_35.txt AC 104 ms 4992 KB
1_36.txt AC 26 ms 4480 KB
1_37.txt AC 52 ms 3712 KB
1_38.txt AC 126 ms 10368 KB
1_39.txt AC 43 ms 6656 KB
1_40.txt AC 121 ms 9600 KB
1_41.txt AC 65 ms 9472 KB
1_42.txt AC 106 ms 6656 KB
1_43.txt AC 117 ms 9344 KB
1_44.txt AC 109 ms 8064 KB
1_45.txt AC 30 ms 3840 KB
1_46.txt AC 132 ms 9984 KB
1_47.txt AC 40 ms 4736 KB
1_48.txt AC 44 ms 3712 KB
1_49.txt AC 19 ms 3584 KB
1_50.txt AC 79 ms 6272 KB
1_51.txt AC 116 ms 8192 KB
1_52.txt AC 15 ms 5632 KB
1_53.txt AC 29 ms 6016 KB
1_54.txt AC 53 ms 5504 KB
1_55.txt AC 50 ms 3712 KB
1_56.txt AC 83 ms 7168 KB
1_57.txt AC 122 ms 8576 KB
1_58.txt AC 111 ms 8704 KB
1_59.txt AC 11 ms 4352 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