Submission #656415

#	Time	Username	Problem	Language	Result	Execution time	Memory
656415		Dorost	T-Covering (eJOI19_covering)	C++17	100 / 100	152 ms	102400 KiB

covering

/* 	* In the name of GOD  */

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
#define F first
#define S second
#define mk make_pair
const int N = 1012345, NI = -1123456789;
int n, m, k, ans = 0, t = 0;
vector <int> a[N];
vector <bool> mr[N];
int vis[N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, dx2[4] = {-1, 1, 1, -1}, dy2[4] = {1, 1, -1, -1}, bad[N], mn[N], ch[N];
vector <int> g[N];

bool val (int x, int y) {
	return ((x >= 1) && (y >= 1) && (x <= n) && (y <= m));
}

int h(int x, int y) {
	return (x - 1) * m + y;
}

void hal (int x, int y, int d) {
	mr[x][y] = false;
	ans += a[x][y];
	a[x][y] = NI;
	for (int i = 0; i < 4; i++) {
		if (i == d)
			continue;
		ans += a[x + dx[i]][y + dy[i]];
		a[x + dx[i]][y + dy[i]] = NI;
	}
}

void dfs (int v, int p) {
	vis[v] = 1;
	int x = (v - 1) / m + 1, y = (v - 1) % m + 1;
	for (int i = 0; i < 4; i++) 
		mn[t] = min(a[x + dx[i]][y + dy[i]], mn[t]);
	for (int u : g[v]) {
		if (u == p)
			continue;
		if (!vis[u])
			dfs(u, v);
		else if (vis[u] == 1) { 
			bad[t]++;
		}
	}
	vis[v] = 2;
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	cin >> n >> m;
	for (int i = 0; i < n + 5; i++)
		for (int j = 0; j < m + 5; j++) {
			mr[i].push_back(false);
			a[i].push_back(NI);
		}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	cin >> k;
	for (int i = 1; i <= k; i++) {
		int x, y;
		cin >> x >> y;
		x++;
		y++;
		mr[x][y] = true;
	}
	for (int x = 1; x <= n; x++) {
		for (int y = 1; y <= m; y++) {
			for (int i = 0; i < 4; i++) {
				if (mr[x][y] && mr[x + dx[i]][y + dy[i]]) {
					hal (x, y, i);
					hal (x + dx[i], y + dy[i], (i + 2) & 3);
				}
				if (mr[x][y] && mr[x + dx2[i]][y + dy2[i]]) {
					hal (x, y, i);
					hal (x + dx2[i], y + dy2[i], (i + 2) & 3);
				}
			}
		}
	}
	for (int x = 1; x <= n; x++) 
		for (int y = 1; y <= m; y++) {
			if (!mr[x][y])
				continue;
			ans += a[x][y];
			for (int i = 0; i < 4; i++) {
				ans += a[x + dx[i]][y + dy[i]];
			}
		}
	for (int x = 1; x <= n; x++) {
		for (int y = 1; y <= m; y++) {
			for (int i = 0; i < 2; i++) {
				if (val(x + 2 * dx[i], y + 2 * dy[i]) && mr[x][y] && mr[x + 2 * dx[i]][y + 2 * dy[i]]) {
					int l = h(x, y);
					int r = h(x + 2 * dx[i], y + 2 * dy[i]);
					ans -= a[x + dx[i]][y + dy[i]];
					g[l].push_back(r);
					g[r].push_back(l);
				}
			}
		}
	}
	for (int x = 1; x <= n; x++) {
		for (int y = 1; y <= m; y++) {
			if (!mr[x][y]) {
				continue;
			}
			int v = h(x, y);
			if (vis[v])
				continue;
			++t;
			mn[t] = -NI;
			dfs(v, v);
			if (bad[t] > 1) {
				cout << "No";
				exit(0);
			}
			if (bad[t] == 0)
				ans -= mn[t];
		}
	}
	if (ans < 0) {
		cout << "No";
	} else {
		cout << ans;
	}
}

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