Submission #498489

#	Time	Username	Problem	Language	Result	Execution time	Memory
498489		uncripted	T-Covering (eJOI19_covering)	C++11	0 / 100	48 ms	102404 KiB

covering

#include<bits/stdc++.h>
#define f first
#define se second
#define pb push_back
using namespace std;
 
long long ss=0;
long long size=0;
multiset<long long> t;
long long nsize=0;
	long long a[5000][5000];	
	long long r[5000][5000];
	long long fix[5000][5000];
	long long gr[5000][5000];
	long long vis[5000][5000];
	
	vector<pair<long long,long long> > adj[5000][5000];
void dfs(pair<long long,long long> p){
	vis[p.f][p.se]=1;
	nsize++;
	if(vis[p.f-1][p.se]!=1){
		size++;
	}
		if(vis[p.f+1][p.se]!=1){
		size++;
	}
		if(vis[p.f][p.se-1]!=1){
		size++;
	}
		if(vis[p.f][p.se+1]!=1){
		size++;
	}
	t.insert(a[p.f-1][p.se]);
	t.insert(a[p.f+1][p.se]);
	t.insert(a[p.f][p.se-1]);
	t.insert(a[p.f][p.se+1]);
	vis[p.f-1][p.se]=1;
	vis[p.f+1][p.se]=1;
	vis[p.f][p.se-1]=1;
	vis[p.f][p.se+1]=1;
	for(long long i=0; i<adj[p.f][p.se].size(); i++){
		if(vis[adj[p.f][p.se][i].f][adj[p.f][p.se][i].se]){
			continue;
		}
		dfs({adj[p.f][p.se][i].f, adj[p.f][p.se][i].se});
	}
}
int main(){
	long long n,m;
	cin>>n>>m;
 
	for(long long i=0; i<n; i++){
		for (long long j=0; j<m; j++){
			cin>>a[i][j];
			r[i][j]=0;
			fix[i][j]=0;
			gr[i][j]=0;
			vis[i][j]=0;
		}
	}
	long long k;
	cin>>k;
	pair<long long,long long> c[k];
 
 
	for(long long i=0; i<k; i++){
		cin>>c[i].f>>c[i].se;
		r[c[i].f][c[i].se]=1;
	}
	long long pas=0;
	pair<long long,long long> d[8]={{1,1}, {1,0}, {1,-1}, {0,1}, {0, -1}, {-1,1}, {-1, 0}, {-1,-1}};
	for(long long i=0; i<n; i++){
		for(long long j=0; j<m; j++){
			long long p=0;
			
			for(long long ii=0; ii<8; ii++){
				long long x=i+d[ii].f;
				long long y=j+d[ii].se;
				if(r[i][j]==1 && r[x][y]==1){
					p++;	
					if(i+1>=n || i-1<0 || j-1<0 || j+1>=m || x+1>=n || x-1<0 || y-1<0 || y+1>=m){
						cout<<"No"<<endl;
						return 0;
					}
					fix[i][j]=1;
					fix[i+1][j]=1;
					fix [i-1][j]=1;
					fix[i][j-1]=1;
					fix[i][j+1]=1;
					fix[x][y]=1;
					fix[x+1][y]=1;
					fix[x-1][y]=1;
					fix[x][y-1]=1;
					fix[x][y+1]=1;
				
				}
			}
			if(p>1){
				cout<<"No"<<endl;
				return 0;
			}
			
		}
	}
	for(long long asd=0; asd<k; asd++){
	
		for(long long i=0; i<k; i++){
			
		long long x=c[i].f,y=c[i].se;
		if(fix[x][y]==1){
			continue;
		}
		long long bruh=4;
		bool left=true,right=true,up=true,down=true;
		if(x+1>=n){
			bruh--;
			up=false;
		}else if(fix[x+1][y]==1 || r[x+1][y]==1){
			bruh--;
			up=false;
		}
		if(x-1<0){
			bruh--;
			down=false;
		}else if(fix[x-1][y]==1 || r[x-1][y]==1){
				bruh--;
				down=false;
		}
		if(y-1<0){
			bruh--;
			left=false;
		}else if(fix[x][y-1]==1 || r[x][y-1]==1){
			bruh--;
			left=false;
		}
		if( y+1>=m){
			bruh--;
			right=false;
		}else if(fix[x][y+1]==1 || r[x][y+1]==1){
				bruh--;
			right=false;
		}
		if(bruh==3){
			fix[x][y]=1;
			if(up==true){
			fix[x+1][y]=1;	
			}
			if(down==true){
			fix[x-1][y]=1;	
			}
			if(left==true){
			fix[x][y-1]=1;	
			}
			if(right==true){
			fix[x][y+1]=1;	
			}
			
		}
		if(bruh<3){
			cout<<"No";
			return 0;
		}
		if(bruh==4){
			gr[x][y]=1;
		}
	}	
	
	}
	for(long long i=0; i<n; i++){
		for(long long j=0; j<m; j++){
			if(gr[i][j]==0){
				continue;
			}
			if(i+2<n){
				if(gr[i+2][j]==1){
					adj[i][j].pb({i+2,j});
				}
			}
			if(i-2>=0){
				
				if(gr[i-2][j]==1){
					adj[i][j].pb({i-2,j});
				}
			}
			if(j+2<m){
				
				if(gr[i][j+2]==1){
					adj[i][j].pb({i,j+2});
				}
			}
			if(j-2>=0){
				
				if(gr[i][j-2]==1){
					adj[i][j].pb({i,j-2});
				}
			}
		}
	}
	for(long long i=0; i<n; i++){
		for(long long j=0; j<m; j++){
			if(vis[i][j]==0 && gr[i][j]==1 ){
				dfs({i,j});
				if(size==3*nsize+1){
					ss+=*t.begin();
				}
				if(size<3*nsize){
					cout<<"No"<<endl;
					return 0;
				}
				t.clear();
			}
		}
	}
	for(long long i=0; i<n; i++){
		for(long long j=0; j<m; j++){
			if(fix[i][j]==1 || vis[i][j]==1){
				pas+=a[i][j];
			}
		}
	}
 
	cout<<pas-ss;
}

Compilation message (stderr)

covering.cpp: In function 'void dfs(std::pair<long long int, long long int>)':
covering.cpp:41:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(long long i=0; i<adj[p.f][p.se].size(); i++){
      |                     ~^~~~~~~~~~~~~~~~~~~~~~

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