Submission #642361

#	Time	Username	Problem	Language	Result	Execution time	Memory
642361		AmirAli_H1	T-Covering (eJOI19_covering)	C++17	100 / 100	143 ms	20504 KiB

covering

// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;

#define all(x)		(x).begin(),(x).end()
#define len(x)		((ll) (x).size())
#define F		first
#define S		second
#define pb		push_back
#define sep             ' '
#define endl            '\n'
#define Mp		make_pair
#define debug(x)	cerr << #x << ": " <<  x << endl;
#define kill(x)		cout << x << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define file_io(x,y)	freopen(x, "r", stdin); freopen(y, "w", stdout);

int n, m, k;
ll output;
const int maxn = 1e6 + 3;
int a[maxn];
int mark[maxn];
int col[maxn]; int c = 1;
pii cl[maxn];
queue<pii> qu; vector<pair<ll, pii>> vc;

int GI(int i, int j) {
	return (i * m + j);
}

void solve1(int x, int y) {
	int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1};
	if (mark[GI(x, y)] == 2) return ;
	qu.push(Mp(x, y));
	while (!qu.empty()) {
		int r = 0;
		x = qu.front().F, y = qu.front().S;
		qu.pop();
		for (int x1 : {x - 1, x + 1}) {
			for (int y1 : {y - 1, y + 1}) {
				if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && mark[GI(x1, y1)] == 1) {
					r -= 1;
				}
			}
		}
		if (r == -1) {
			mark[GI(x, y)] = 2;
			output += a[GI(x, y)];
			vector<pii> vc;
			for (int T = 0; T < 4; T++) {
				int x1 = x + dx[T], y1 = y + dy[T];
				if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !mark[GI(x1, y1)]) {
					mark[GI(x1, y1)] = 2;
					output += a[GI(x1, y1)];
					vc.pb(Mp(x1, y1));
				}
			}
			int xr = -1, yr = -1;
			for (int x1 : {x - 1, x + 1}) {
				for (int y1 : {y - 1, y + 1}) {
					if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && mark[GI(x1, y1)] == 1) {
						xr = x1; yr = y1;
						break;
					}
				}
				if (xr != -1) break;
			}
			mark[GI(xr, yr)] = 2;
			output += a[GI(xr, yr)];
			for (int T = 0; T < 4; T++) {
				int x1 = xr + dx[T], y1 = yr + dy[T];
				if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !mark[GI(x1, y1)]) {
					mark[GI(x1, y1)] = 2;
					output += a[GI(x1, y1)];
					vc.pb(Mp(x1, y1));
				}
			}
			if (len(vc) != 6) {
				kill("No");
			}
			for (auto f : vc) {
				int x1 = f.F, y1 = f.S;
				for (int R = 0; R < 4; R++) {
					int x2 = x1 + dx[R], y2 = y1 + dy[R];
					if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m && mark[GI(x2, y2)] == 1) {
						qu.push(Mp(x2, y2));
					}
				}
			}
			continue;
		}
		else if (r < -1) {
			kill("No");
		}
		
		r = 0;
		for (int T = 0; T < 4; T++) {
			int x1 = x + dx[T], y1 = y + dy[T];
			if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !mark[GI(x1, y1)]) {
				r += 1;
			}
		}
		if (r < 3) {
			kill("No");
		}
		else if (r == 3) {
			mark[GI(x, y)] = 2;
			output += a[GI(x, y)];
			vector<pii> vc;
			for (int T = 0; T < 4; T++) {
				int x1 = x + dx[T], y1 = y + dy[T];
				if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !mark[GI(x1, y1)]) {
					mark[GI(x1, y1)] = 2;
					output += a[GI(x1, y1)];
					vc.pb(Mp(x1, y1));
				}
			}
			for (auto f : vc) {
				int x1 = f.F, y1 = f.S;
				for (int R = 0; R < 4; R++) {
					int x2 = x1 + dx[R], y2 = y1 + dy[R];
					if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m && mark[GI(x2, y2)] == 1) {
						qu.push(Mp(x2, y2));
					}
				}
			}
		}
	}
}

void solve2(int x, int y) {
	int dx[4] = {-2, 2, 0, 0}; int dy[4] = {0, 0, -2, 2};
	int rx[4] = {-1, 1, 0, 0}; int ry[4] = {0, 0, -1, 1};
	if (mark[GI(x, y)] == 2 || col[GI(x, y)] != 0) return ;
	col[GI(x, y)] = c;
	qu.push(Mp(x, y));
	int deg = 0, l = 0;
	vc.clear();
	while (!qu.empty()) {
		x = qu.front().F, y = qu.front().S;
		output += a[GI(x, y)];
		l += 1;
		qu.pop();
		for (int T = 0; T < 4; T++) {
			int x1 = x + rx[T], y1 = y + ry[T];
			if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && !mark[GI(x1, y1)]) {
				mark[GI(x1, y1)] = 2;
				vc.pb(Mp(a[GI(x1, y1)], Mp(x1, y1)));
			}
		}
		for (int T = 0; T < 4; T++) {
			int x1 = x + dx[T], y1 = y + dy[T];
			if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && mark[GI(x1, y1)] == 1) {
				deg += 1;
				if (col[GI(x1, y1)] == 0) {
					col[GI(x1, y1)] = c;
					qu.push(Mp(x1, y1));
				}
			}
		}
	}
	int eds_num = deg / 2;
	sort(all(vc), greater<pair<ll, pii>>());
	if (eds_num == l) {
		if (len(vc) < 3 * l) kill("No");
		for (auto f : vc) {
			output += f.F;
		}
	}
	else if (eds_num == l - 1) {
		if (len(vc) < 3 * l) kill("No");
		if (len(vc) == 3 * l + 1) {
			auto f = vc[len(vc) - 1];
			int x1 = f.S.F, y1 = f.S.S;
			mark[GI(x1, y1)] = 0;
			vc.pop_back();
		}
		for (auto f : vc) {
			output += f.F;
		}
	}
	else {
		kill("No");
	}
	c++;
	return ;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[GI(i, j)];
		}
	}
	
	int k;
	cin >> k;
	for (int i = 0; i < k; i++) {
		int x, y;
		cin >> x >> y;
		cl[i].F = x; cl[i].S = y;
		mark[GI(x, y)] = 1;
	}
	
	for (int i = 0; i < k; i++) {
		solve1(cl[i].F, cl[i].S);
	}
	
	for (int i = 0; i < k; i++) {
		solve2(cl[i].F, cl[i].S);
	}
	
	cout << output << endl;
	
	return 0;
}

• 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