제출 #684846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684846		US3RN4M3	T-Covering (eJOI19_covering)	C++17	0 / 100	16 ms	24628 KiB

covering

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 1005;
int val[mx][mx];
int sid[mx][mx];
bool g_vis[mx*mx];
int n, m;
int dx1[4] = {1, 1, 1, 0};
int dy1[4] = {1, 0, -1, 1};
int dx2[4] = {2, 0};
int dy2[4] = {0, 2};
int dx3[4] = {1, -1, 0, 0};
int dy3[4] = {0, 0, 1, -1};
int dx4[5] = {0, 1, -1, 0, 0};
int dy4[5] = {0, 0, 0, -1, 1};
vector<pair<int, int>> heavy_edges;
vector<pair<int, int>> light_edges;
int g_idx[mx*mx];
vector<int> g_vec[mx*mx];
int g_best[mx*mx];
int g_bad[mx*mx];
void add_light(int a, int b) {
	if(g_vec[g_idx[a]].size() > g_vec[g_idx[b]].size()) swap(a, b);
	g_best[g_idx[b]] = min(g_best[g_idx[b]], g_best[g_idx[a]]);
	g_bad[g_idx[b]] += g_bad[g_idx[a]];
	vector<int> & a_vec = g_vec[a];
	for(int i : a_vec) {
		g_idx[i] = g_idx[b];
		g_vec[g_idx[b]].push_back(i);
	}
	g_bad[g_idx[b]]++;
}
void add_heavy(int a, int b) {
	add_light(a, b);
	g_bad[g_idx[b]]++;
}
main() {
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> val[i][j];
		}
	}
	int cnt_spec;
	cin >> cnt_spec;
	vector<pair<int, int>> spec(cnt_spec + 1);
	for(int i = 1; i <= cnt_spec; i++) {
		int x, y; cin >> x >> y;
		spec[i] = {x, y};
		sid[x][y] = i;
	}
	for(int i = 1; i <= cnt_spec; i++) {
		auto [x, y] = spec[i];
		for(int dir = 0; dir < 4; dir++) {
			int nx = x + dx1[dir];
			int ny = y + dy1[dir];
			if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if(!sid[nx][ny]) continue;
			heavy_edges.push_back({i, sid[nx][ny]});
		}
		for(int dir = 0; dir < 2; dir++) {
			int nx = x + dx2[dir];
			int ny = y + dy2[dir];
			if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if(!sid[nx][ny]) continue;
			light_edges.push_back({i, sid[nx][ny]});
		}
	}
	for(int i = 0; i <= cnt_spec; i++) {
		g_idx[i] = i;
		g_vec[i] = {i};
		g_best[i] = 1e9;
		g_bad[i] = 0;
		auto [x, y] = spec[i];
		for(int dir = 0; dir < 4; dir++) {
			int nx = x + dx1[dir];
			int ny = y + dy1[dir];
			if(nx < 0 || ny < 0 || nx >= n || ny >= m) {
				g_bad[i]++;
			} else g_best[i] = min(g_best[i], val[nx][ny]);
		}
	}
	for(auto [a, b] : light_edges) add_light(a, b);
	for(auto [a, b] : heavy_edges) add_heavy(a, b);
	ll rem = 0;
	for(int i = 1; i <= cnt_spec; i++) {
		int id = g_idx[i];
		if(g_vis[id]) continue;
		if(g_bad[id] > g_vec[id].size()) {
			cout << "No" << endl;
			return 0;
		}
		if(g_bad[id] == g_vec[id].size()) continue;
		rem += g_best[id];
	}
	ll ans = 0;
	for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
		bool cond = false;
		for(int dir = 0; dir < 5; dir++) {
			int nx = i + dx4[dir];
			int ny = j + dy4[dir];
			if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if(sid[nx][ny]) cond = true;
		}
		if(cond) ans += val[i][j];
	}
	ans -= rem;
	cout << ans << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

covering.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main() {
      | ^~~~
covering.cpp: In function 'int main()':
covering.cpp:90:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   if(g_bad[id] > g_vec[id].size()) {
      |      ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
covering.cpp:94:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   if(g_bad[id] == g_vec[id].size()) continue;
      |      ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30