Submission #1029204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029204		tolbi	T-Covering (eJOI19_covering)	C++17	100 / 100	219 ms	18012 KiB

covering

#include <bits/stdc++.h>
using namespace std;
template<typename T> istream& operator>>(istream& is, vector<T> &V){for (auto &it : V) is>>it; return is;}
template<typename T> void cls(queue<T> &q) {while (q.size()) q.pop();}
int main(){
	int n,m;cin>>n>>m;
	vector<vector<int>> arr(n,vector<int>(m));
	cin>>arr;
	vector<vector<int>> tr(n,vector<int>(m,0));
	int hh;cin>>hh;
	int ans = 0;
	for (int i = 0; i < hh; i++){
		int x,y;cin>>x>>y;
		tr[x][y]=1;
	}
	bool boolean=true;
	function<bool(int,int)> available = [&](int x, int y)->bool{
		return (x>=0 && x<n && y>=0 && y<m && tr[x][y]==0);
	};
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (tr[i][j]>0){
				if (i && j+1<m && tr[i-1][j+1]>0){
					if (available(i+1,j) && available(i,j-1) && available(i,j+1) && available(i-1,j) && available(i-2,j+1) && available(i-1,j+2)){
						tr[i+1][j]=tr[i][j-1]=tr[i][j+1]=tr[i-1][j]=tr[i-2][j+1]=tr[i-1][j+2]=-1;
						tr[i][j]=tr[i-1][j+1]=-1;
					}
					else {
						boolean=false;
						break;
					}
				}
				if (j+1<m && tr[i][j+1]>0){
					if (available(i,j-1) && available(i+1,j) && available(i-1,j) && available(i,j+2) && available(i+1,j+1) && available(i-1,j+1)){
						tr[i][j-1]=tr[i+1][j]=tr[i-1][j]=tr[i][j+2]=tr[i+1][j+1]=tr[i-1][j+1]=-1;
						tr[i][j]=tr[i][j+1]=-1;
					}
					else {
						boolean=false;
						break;
					}
				}
				if (i+1<n && j+1<m && tr[i+1][j+1]>0){
					if (available(i,j-1) && available(i,j+1) && available(i-1,j) && available(i+1,j) && available(i+2,j+1) && available(i+1,j+2)){
						tr[i][j-1]=tr[i][j+1]=tr[i-1][j]=tr[i+1][j]=tr[i+2][j+1]=tr[i+1][j+2]=-1;
						tr[i][j]=tr[i+1][j+1]=-1;
					}
					else {
						boolean=false;
						break;
					}
				}
				if (i+1<n && tr[i+1][j]>0){
					if (available(i,j-1) && available(i,j+1) && available(i+1,j-1) && available(i+1,j+1) && available(i-1,j) && available(i+2,j)){
						tr[i][j-1]=tr[i][j+1]=tr[i+1][j-1]=tr[i+1][j+1]=tr[i-1][j]=tr[i+2][j]=-1;
						tr[i][j]=tr[i+1][j]=-1;
					}
					else {
						boolean=false;
						break;
					}
				}
			}
		}
		if (!boolean) break;
	}
	if (!boolean){
		cerr<<"No"<<endl;
		cout<<"No"<<endl;
		return 0;
	}
	queue<pair<int,int>> qu;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j){
			if (tr[i][j]<0) qu.push({i,j});
		}
	}
	for (int i = 0; i < n; i++){
		qu.push({i,-1});
		qu.push({i,m});
	}
	for (int j = 0; j < m; j++){
		qu.push({-1,j});
		qu.push({n,j});
	}
	function<void(void)> beniyakkendiniyak = [&](void)->void{
		while (qu.size()){
			int x = qu.front().first;
			int y = qu.front().second;
			qu.pop();
			if (x-1>=0 && y>=0 && y<m && tr[x-1][y]>0){
				x--;
			}
			else if (y-1>=0 && x>=0 && x<n && tr[x][y-1]>0){
				y--;
			}
			else if (x+1<n && y>=0 && y<m && tr[x+1][y]>0){
				x++;
			}
			else if (y+1<m && x>=0 && x<n && tr[x][y+1]>0){
				y++;
			}
			else continue;
			vector<pair<int,int>> avail;
			avail.push_back({x,y});
			if (available(x-1,y)) avail.push_back({x-1,y});
			if (available(x+1,y)) avail.push_back({x+1,y});
			if (available(x,y+1)) avail.push_back({x,y+1});
			if (available(x,y-1)) avail.push_back({x,y-1});
			if (avail.size()!=4){
				boolean=false;
				break;
			}
			for (auto it : avail){
				tr[it.first][it.second]=-1;
				qu.push({it.first,it.second});
			}
		}
	};
	beniyakkendiniyak();
	if (!boolean){
		cout<<"No"<<endl;
		cerr<<"No"<<endl;
		return 0;
	}
	vector<vector<int>> par(n,vector<int>(m,-1));
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (tr[i][j]>0 && par[i][j]==-1){
				qu.push({i,j});
				par[i][j]=-2;
				bool bb = true;
				vector<pair<int,int>> gez;
				while (qu.size()){
					int x = qu.front().first;
					int y = qu.front().second;
					gez.push_back({x,y});
					qu.pop();
					if (x-2>=0 && tr[x-2][y]>0 && par[x][y]!=(x-2)*m+y){
						if (par[x-2][y]!=-1){
							bb=false;
							cls(qu);
							tr[x][y]=tr[x+1][y]=tr[x][y-1]=tr[x][y+1]=-1;
							qu.push({x,y});
							qu.push({x,y+1});
							qu.push({x,y-1});
							qu.push({x+1,y});
							break;
						}
						par[x-2][y]=x*m+y;
						qu.push({x-2,y});
					}
					if (x+2<n && tr[x+2][y]>0 && par[x][y]!=(x+2)*m+y){
						if (par[x+2][y]!=-1){
							bb=false;
							cls(qu);
							tr[x][y]=tr[x-1][y]=tr[x][y-1]=tr[x][y+1]=-1;
							qu.push({x,y});
							qu.push({x,y+1});
							qu.push({x,y-1});
							qu.push({x-1,y});
							break;
						}
						par[x+2][y]=x*m+y;
						qu.push({x+2,y});
					}
					if (y-2>=0 && tr[x][y-2]>0 && par[x][y]!=(x)*m+y-2){
						if (par[x][y-2]!=-1){
							bb=false;
							cls(qu);
							tr[x][y]=tr[x-1][y]=tr[x+1][y]=tr[x][y+1]=-1;
							qu.push({x,y});
							qu.push({x,y+1});
							qu.push({x+1,y});
							qu.push({x-1,y});
							break;
						}
						par[x][y-2]=x*m+y;
						qu.push({x,y-2});
					}
					if (y+2<m && tr[x][y+2]>0 && par[x][y]!=(x)*m+y+2){
						if (par[x][y+2]!=-1){
							bb=false;
							cls(qu);
							tr[x][y]=tr[x-1][y]=tr[x+1][y]=tr[x][y-1]=-1;
							qu.push({x,y});
							qu.push({x,y-1});
							qu.push({x+1,y});
							qu.push({x-1,y});
							break;
						}
						par[x][y+2]=x*m+y;
						qu.push({x,y+2});
					}
				}
				if (qu.size()){
					beniyakkendiniyak();
				}
				else {
					int minel = 1023;
					for (auto it : gez){
						int x = it.first, y = it.second;
						minel=min(minel,arr[x][y-1]);
						minel=min(minel,arr[x][y+1]);
						minel=min(minel,arr[x-1][y]);
						minel=min(minel,arr[x+1][y]);
						tr[x][y]=tr[x-1][y]=tr[x][y+1]=tr[x+1][y]=tr[x][y-1]=-1;
					}
					if (minel!=1023) ans-=minel;
				}
			}
		}
	}
	if (!boolean){
		cout<<"No"<<endl;
		cerr<<"No"<<endl;
		return 0;
	}
	cerr<<"Yep"<<endl;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (tr[i][j]<0) ans+=arr[i][j];
		}
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:133:10: warning: variable 'bb' set but not used [-Wunused-but-set-variable]
  133 |     bool bb = true;
      |          ^~

• 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