Submission #651970

#	Time	Username	Problem	Language	Result	Execution time	Memory
651970		Kahou	T-Covering (eJOI19_covering)	C++14	10 / 100	56 ms	97584 KiB

covering

/* In the name of God, aka Allah */
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mk make_pair
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll inf = 1e9 + 50;
const int N = 1e6 + 50;
int m, n, k; 
vector<ll> grid[N];
vector<int> mark[N];
vector<int> seen[N];
ll mn[N], bk[N];
ll ans;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int d2x[] = {-1, 1, 1, -1};
int d2y[] = {1, 1, -1, -1};
vector<int> adj[N];
bool vis[N];
int t;

void dojob(int x, int y, int d) {
	ans += grid[x][y];
	grid[x][y] = -inf;
	mark[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		if (i == d) continue;
		ans += grid[x+dx[i]][y+dy[i]];
		grid[x+dx[i]][y+dy[i]] = -inf;
	}
}
bool val(int x, int y) {
	return x >= 1 && x <= m && y >= 1 && y <= n;
}

int f(int x, int y) {
	return (x-1)*n + y;
}

void dfs(int u, int p) {
	vis[u] = 1;
	int x = (u+n-1)/n, y = (u+n-1)%n + 1;
	ans += grid[x][y];
	seen[x][y]= 1;
	for (int i = 0; i < 4; i++) {
		if (!val(x+dx[i], y+dy[i]) || seen[x+dx[i]][y+dy[i]]) continue;
		seen[x+dx[i]][y+dy[i]]= 1;
		mn[t] = min(mn[t], grid[x+dx[i]][y+dy[i]]);
		ans += grid[x+dx[i]][y+dy[i]];
	}
	for (int v:adj[u]) {
		if (v == p) continue;
		if (!vis[v]) dfs(v, u);
		else if (vis[v] == 1) bk[t]++;
	}
	vis[u] = 2;
}

void solve() {
	cin >> m >> n;
	for (int i = 0; i <= m+5; i++) {
		grid[i].resize(n+5);
		mark[i].resize(n+5);
		seen[i].resize(n+5);
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> grid[i][j];
		}
	}
	for (int i = 1; i <= n*m; i++) {
		mn[i] = inf;
	}
	cin >> k;
	for (int i = 1; i <= k; i++) {
		int r, c;
		cin >> r >> c;
		r++, c++;
		mark[r][c] = 1;
	}
	for (int x = 1; x <= m; x++) {
		for (int y = 1; y <= n; y++) {
			if (!mark[x][y]) continue;
			if ((x == 1 && y == 1) || \
				(x == 1 && y == n) || \
				(x == m && y == 1) || \
				(x == m && y == n)) {
				cout << "No" << endl;
				return;
			}
			if (x == 1) dojob(x, y, 1);
			else if (y == n) dojob(x, y, 2);
			else if (x == m) dojob(x, y, 3);
			else if (y == 1) dojob(x, y, 4);
			for (int i = 0; i < 4; i++) {
				if (val(x+dx[i], y+dy[i]) && mark[x][y] && mark[x+dx[i]][y+dy[i]]) {
					dojob(x, y, i);
					dojob(x+dx[i], y+dy[i], (i+2)&3);
				}
				if (val(x+d2x[i], y+d2y[i]) && mark[x][y] && mark[x+d2x[i]][y+d2y[i]]) {
					dojob(x, y, i);
					dojob(x+d2x[i], y+d2y[i], (i+2)&3);
				}
			}

		}
	}
	for (int x = 1; x <= m; x++) {
		for (int y = 1; y <= n; y++) {
			if (!mark[x][y]) continue;
			for (int i = 0; i < 2; i++) {
				if (val(x+2*dx[i], y+2*dy[i]) && mark[x+2*dx[i]][y+2*dy[i]]) {
					int u = f(x, y);
					int v = f(x+2*dx[i], y+2*dy[i]);
					adj[u].push_back(v);
					adj[v].push_back(u);
				}
			}
		}
	}
	for (int u = 1; u <= n*m; u++) {
		if (!vis[u] && mark[(u+n-1)/n][(u+n-1)%n + 1]) {
			t++;
			dfs(u, 0);
			if (bk[t] >= 2) {
				cout << "No" << endl;
				return;
			}
			if (!bk[t]) ans -= mn[t];
		}
	}
	if (ans < 0) {
		cout << "No" << endl;
		return;
	}
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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