Submission #398043

#	Time	Username	Problem	Language	Result	Execution time	Memory
398043		nvujica	T-Covering (eJOI19_covering)	C++14	100 / 100	119 ms	18416 KiB

covering

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 1e6 + 10;

int n, m, k, x, y, ans;
vector <vector <int> > a;
vector <vector <int> > red;
vector <vector <int> > bio;
vector <vector <int> > ubr;
int dx[4] = {-2, 0, 0, 2};
int dy[4] = {0, -2, 2, 0};
queue <pair<int, int> > q;

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

int bfs(int pocx, int pocy){
	q.push({pocx, pocy});
	bio[pocx][pocy] = 1;
	
	int cik = 0, sus = 0, vani = 0, mini = 1005, sum = 0;
	
	while(!q.empty()){
		int x = q.front().fi;
		int y = q.front().se;
		q.pop();
		
		cik += bio[x][y] - 1;
		
		for(int i = -1; i <= 1; i++){
			for(int j = -1; j <= 1; j++){
				if(i * j != 0) continue;
				
				int x2 = x + i;
				int y2 = y + j;
				
				if(!ok(x2, y2)){
					vani++;
					continue;
				}
				if(ubr[x2][y2]) continue;
				
				sum += a[x2][y2];
				if(i | j) mini = min(mini, a[x2][y2]);
				ubr[x2][y2] = 1;
			}
		}
		
		for(int i = -1; i <= 1; i++){
			for(int j = -1; j <= 1; j++){					
				int x2 = x + i;
				int y2 = y + j;
				
				if(!ok(x2, y2)) continue;
				if(!red[x2][y2]) continue;		
				if(bio[x2][y2]){
					bio[x2][y2]++;
					continue;
				}
				
				sus++;
				bio[x2][y2] = 1;
				q.push({x2, y2});
			}
		}
				
		for(int i = 0; i < 4; i++){
			int x2 = x + dx[i];
			int y2 = y + dy[i];
			
			if(!ok(x2, y2)) continue;
			if(!red[x2][y2]) continue;			
			if(bio[x2][y2]){
				bio[x2][y2]++;
				continue;
			}
			
			bio[x2][y2] = 1;
			q.push({x2, y2});
		}
	}
	
	//cout << cik << ' ' << sus << ' ' << vani << endl;
	 
	if(cik + sus + vani > 1) return -1;
	if(cik + sus + vani == 1) return sum;
	return sum - mini;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	
	vector <int> v(m, 0);
	
	for(int i = 0; i < n; i++){
		a.push_back(v);
		red.push_back(v);
		bio.push_back(v);
		ubr.push_back(v);
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> x;
			a[i][j] = x;
		}
	}
	
	cin >> k;
	
	for(int i = 0; i < k; i++){
		cin >> x >> y;
		red[x][y] = 1;
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(red[i][j] && !bio[i][j]){
				
				int sol = bfs(i, j);
				
				if(sol == -1){
					cout << "No";
					return 0;
				}
				else ans += sol;
			}
		}
	}
	
	cout << ans;
	
	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