Submission #629670

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
629670	2022-08-14T21:33:11 Z	lovrot	T-Covering (eJOI19_covering)	C++11	100 / 100	175 ms	46632 KB

covering

#include <bits/stdc++.h> 
#include <unistd.h>

#define X first
#define Y second
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define vec vector
#define pri(i, poc, n, pov) for(int i = (int) poc; i < (int) n; i += (int) pov)
#define od(i, poc, n, pov) for(int i = (int) poc; i > (int) n; i -= (int) pov)

using namespace std;

const int INF = 1e9;
const int lx[8] = {1, -1, 0, 0, -1, 1, 1, -1};
const int ly[8] = {0, 0, 1, -1, -1, 1, -1, 1};
const int N = 1e6 + 10;

int n, m, q;
int cdeg[N], vis[N];

vec<vec<int>> mat, spec;
vec<vec<bool>> bio, xp;
vec<pii> vx;
vec<int> g[N];

void fail(){ 
	cout << "No\n";
	exit(0);
}

void success(){ 
	int ans = 0;
	pri(i, 1, n + 1, 1) 
		pri(j, 1, m + 1, 1)
			ans += (bio[i][j] ? mat[i][j] : 0);
	cout << ans << "\n";
}

void markPlus(int x, int y){ 
	bio[x][y] = 1;
	pri(i, 0, 4, 1)
		bio[x + lx[i]][y + ly[i]] = 1;
}

void countBan(int x, int y){ 
	int cnt = bio[x][y];
	pri(i, 0, 4, 1){ 
		cnt += bio[x + lx[i]][y + ly[i]];
	}
	if(cnt > 1) fail(); 
}

void tryPlace(int x, int y){ 
	countBan(x, y);
	markPlus(x, y);
}

pii findLow(int x, int y){ 
	pii ret;
	int mn = INF;
	pri(i, 0, 4, 1)
		if(mat[x + lx[i]][y + ly[i]] < mn){ 
			mn = mat[x + lx[i]][y + ly[i]];
			ret = {x + lx[i], y + ly[i]};
		}
	return ret;
}

//+
vec<vec<int>> createMat(int h, int w){ 
	vec<vec<int>> ret;
	pri(i, 0, h, 1){
		vec<int> line;
		pri(j, 0, w, 1) 
			line.pb(0);
		ret.pb(line);
	}
	return ret;
}

//+
vec<vec<bool>> createBio(int h, int w){ 
	vec<vec<bool>> ret;
	pri(i, 0, h, 1){
		vec<bool> line;
		pri(j, 0, w, 1) 
			line.pb(0);
		ret.pb(line);
	}
	return ret;
}

bool isCyc(int u, int p){
	if(vis[u]) return true; 
	vis[u] = true;
	for(int v : g[u]){ 
		if(v != p && vis[v]){ 
			vis[u] = false;
			return true;
		}
		if(v == p) continue;
		if(isCyc(v, u)) {
			vis[u] = false;
			return true;
		}
	}
	vis[u] = false;
	return false;
}

pii rek2(int u){ 
	pii ret = {1, g[u].size()};
	vis[u] = true;
	markPlus(vx[u].X, vx[u].Y);
	for(int v : g[u]){ 
		//cout << u << " " << v << "\n";
		if(vis[v]) continue;
		pii res = rek2(v);
		ret.X += res.X;
		ret.Y += res.Y;
	}	
	return ret;
}

pii rek(int u){ 
	if(vis[u]) return {0, 0};
	vis[u] = true;
	tryPlace(vx[u].X, vx[u].Y);
	pii p = findLow(vx[u].X, vx[u].Y);
	for(int v : g[u]){ 
		if(vis[v]) continue;
		pii res = rek(v);
		if(mat[p.X][p.Y] > mat[res.X][res.Y])
			swap(p, res);
	}
	return p;
}

void init(){ 
	cin >> n >> m;
	
	bio = createBio(n + 2, m + 2);	
	xp = createBio(n + 2, m + 2);
	mat = createMat(n + 2, m + 2);
	spec = createMat(n + 2, m + 2);

	mat[0][0] = INF;

	pri(i, 1, n + 1, 1)
		pri(j, 1, m + 1, 1) 
			cin >> mat[i][j];
	// pri(i, 0, n + 2, 1) 
	// 	xp[i][0] = xp[i][m + 1] = 1;
	// pri(i, 0, m + 2, 1){ 
	// 	xp[0][i] = xp[n + 1][i] = 1;
	// }

	cin >> q;

	pri(i, 0, q, 1){ 
		int x, y;
		cin >> x >> y;
		x++;
		y++;
		vx.pb({x, y});
		xp[x][y] = true;
		spec[x][y] = i + 1;
	}
}

int main(){ 
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	init();

	// cout << "da\n";
	//close edges
	pri(i, 0, q, 1){ 
		int x = vx[i].X;
		int y = vx[i].Y;
		pri(j, 0, 8, 1){ 
			int nx = x + lx[j];
			int ny = y + ly[j];
			if(xp[nx][ny] || (nx == 0 && ny == y) || (nx == n + 1 && ny == y) || (ny == 0 && nx == x) || (ny == m + 1 && nx == x)){ 
				cdeg[i]++;
			}
			if(j < 4){ 
				nx += lx[j];
				ny += ly[j];
				if(nx > 0 && nx < n + 1 && ny > 0 && ny < m + 1 && spec[nx][ny])
					g[i].pb(spec[nx][ny] - 1);
			}
		}
		// cout << i << " " << cdeg[i] << "\n";
		if(cdeg[i] > 1) fail();
		if(cdeg[i] == 1){
			vis[i] = true;	
			markPlus(x, y);
		} 
	}

	//cover groups touching close-pairs
	pri(i, 0, q, 1){ 
		if(cdeg[i] == 1){ 
			for(int v : g[i]){
				if(cdeg[v] == 1) fail();
				rek(v);
			}
		}
	}

	
	pri(i, 0, q, 1){ 
		if(vis[i]) continue;
		bool res = isCyc(i, -1);
		if(!res){ 
			pii p = rek(i);
			bio[p.X][p.Y] = false;
		} else { 
			pii ret = rek2(i);
			if(ret.X - ret.Y / 2 < 0) fail();	
		}
	}
	// pri(i, 1, n + 1, 1)
	// 	pri(j, 1, m + 1, 1)
	// 		cout << bio[i][j] << " \n"[j == m];
	success();
	return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23892 KB	Output is correct
2	Correct	15 ms	24140 KB	Output is correct
3	Correct	20 ms	25044 KB	Output is correct
4	Correct	36 ms	27540 KB	Output is correct
5	Correct	86 ms	35932 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	23928 KB	Output is correct
2	Correct	15 ms	24144 KB	Output is correct
3	Correct	22 ms	24660 KB	Output is correct
4	Correct	36 ms	27540 KB	Output is correct
5	Correct	87 ms	35960 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23892 KB	Output is correct
2	Correct	15 ms	24256 KB	Output is correct
3	Correct	21 ms	25044 KB	Output is correct
4	Correct	53 ms	27540 KB	Output is correct
5	Correct	92 ms	35936 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	13 ms	23764 KB	Output is correct
3	Correct	18 ms	24500 KB	Output is correct
4	Correct	15 ms	24148 KB	Output is correct
5	Correct	20 ms	25236 KB	Output is correct

Subtask #5

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	12 ms	23764 KB	Output is correct
3	Correct	15 ms	23820 KB	Output is correct
4	Correct	14 ms	23764 KB	Output is correct
5	Correct	12 ms	23764 KB	Output is correct

Subtask #6

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23892 KB	Output is correct
2	Correct	15 ms	24140 KB	Output is correct
3	Correct	20 ms	25044 KB	Output is correct
4	Correct	36 ms	27540 KB	Output is correct
5	Correct	86 ms	35932 KB	Output is correct
6	Correct	18 ms	23928 KB	Output is correct
7	Correct	15 ms	24144 KB	Output is correct
8	Correct	22 ms	24660 KB	Output is correct
9	Correct	36 ms	27540 KB	Output is correct
10	Correct	87 ms	35960 KB	Output is correct
11	Correct	13 ms	23892 KB	Output is correct
12	Correct	15 ms	24256 KB	Output is correct
13	Correct	21 ms	25044 KB	Output is correct
14	Correct	53 ms	27540 KB	Output is correct
15	Correct	92 ms	35936 KB	Output is correct
16	Correct	12 ms	23764 KB	Output is correct
17	Correct	13 ms	23764 KB	Output is correct
18	Correct	18 ms	24500 KB	Output is correct
19	Correct	15 ms	24148 KB	Output is correct
20	Correct	20 ms	25236 KB	Output is correct
21	Correct	13 ms	23968 KB	Output is correct
22	Correct	19 ms	24280 KB	Output is correct
23	Correct	20 ms	24976 KB	Output is correct
24	Correct	35 ms	27540 KB	Output is correct
25	Correct	92 ms	35940 KB	Output is correct

Subtask #7

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23892 KB	Output is correct
2	Correct	15 ms	24140 KB	Output is correct
3	Correct	20 ms	25044 KB	Output is correct
4	Correct	36 ms	27540 KB	Output is correct
5	Correct	86 ms	35932 KB	Output is correct
6	Correct	18 ms	23928 KB	Output is correct
7	Correct	15 ms	24144 KB	Output is correct
8	Correct	22 ms	24660 KB	Output is correct
9	Correct	36 ms	27540 KB	Output is correct
10	Correct	87 ms	35960 KB	Output is correct
11	Correct	13 ms	23892 KB	Output is correct
12	Correct	15 ms	24256 KB	Output is correct
13	Correct	21 ms	25044 KB	Output is correct
14	Correct	53 ms	27540 KB	Output is correct
15	Correct	92 ms	35936 KB	Output is correct
16	Correct	12 ms	23764 KB	Output is correct
17	Correct	13 ms	23764 KB	Output is correct
18	Correct	18 ms	24500 KB	Output is correct
19	Correct	15 ms	24148 KB	Output is correct
20	Correct	20 ms	25236 KB	Output is correct
21	Correct	12 ms	23764 KB	Output is correct
22	Correct	12 ms	23764 KB	Output is correct
23	Correct	15 ms	23820 KB	Output is correct
24	Correct	14 ms	23764 KB	Output is correct
25	Correct	12 ms	23764 KB	Output is correct
26	Correct	13 ms	23968 KB	Output is correct
27	Correct	19 ms	24280 KB	Output is correct
28	Correct	20 ms	24976 KB	Output is correct
29	Correct	35 ms	27540 KB	Output is correct
30	Correct	92 ms	35940 KB	Output is correct
31	Correct	175 ms	46632 KB	Output is correct
32	Correct	86 ms	36212 KB	Output is correct
33	Correct	147 ms	41196 KB	Output is correct
34	Correct	86 ms	36212 KB	Output is correct
35	Correct	112 ms	40872 KB	Output is correct