Submission #498585

#	Time	Username	Problem	Language	Result	Execution time	Memory
498585		uncripted	T-Covering (eJOI19_covering)	C++11	100 / 100	624 ms	71540 KiB

covering

#include<bits/stdc++.h>
#define f first
#define se second
#define pb push_back
using namespace std;
 
long long size=0;
set<pair<long long, pair<long long,long long> > > t;
long long nsize=0;
	long long n,m;
	
	long long fix[1012*1012];
	vector<long long> adj[1012*1012];
	
	
	long long r[1010*1010];
 	long long a[1010*1012];
void dfs(long long p){
	long long x=p/m,y=p%m;
		fix[(x)*m+y]=1;
	nsize++;

	if(fix[(x-1)*m+(y)]!=1){
		size++;
		
	}
		if(fix[(x+1)*m+(y)]!=1){
		size++;

	}
		if(fix[(x)*m+(y+1)]!=1){
		size++;
	}
		if(fix[(x)*m+(y-1)]!=1){
		size++;

	}
	t.insert({a[(x+1)*m+(y)],{x+1,y}});	
	t.insert({a[(x)*m+(y-1)],{x,y-1}});	
	t.insert({a[(x)*m+(y+1)],{x,y+1}});
	t.insert({a[(x-1)*m+(y)], {x-1,y}});
	fix[(x-1)*m+(y)]=1;
	fix[(x+1)*m+(y)]=1;
	fix[(x)*m+(y-1)]=1;
	fix[(x)*m+(y+1)]=1;
	for(long long i=0; i<adj[p].size(); i++){
		
		if(fix[adj[p][i]]==1){
			continue;
		}
		dfs(adj[p][i]);
	}
}
void dfs2(int p){
	int x=p/m; int y=p%m;
	if(r[x*m+y]==0){
		return;
	}
		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)*m+y]==1 || r[(x+1)*m+y]==1){
			bruh--;
			up=false;
		}
		if(x-1<0){
			bruh--;
			down=false;
		}else if(fix[(x-1)*m+y] || r[(x-1)*m+y]==1){
				bruh--;
				down=false;
		}
		if(y-1<0){
			bruh--;
			left=false;
		}else if(fix[(x)*m+y-1]==1 || r[(x)*m+y-1]==1){
			bruh--;
			left=false;
		}
		if( y+1>=m){
			bruh--;
			right=false;
		}else if(fix[(x)*m+y+1]==1 || r[(x)*m+y+1]==1){
				bruh--;
			right=false;
		}
			if(bruh==3){
			fix[(x)*m+y]=1;
			if(up==true){
			fix[(x+1)*m+y]=1;
		
			}
			if(down==true){
			fix[(x-1)*m+y]=1;
			
			}
			if(left==true){
			fix[(x)*m+y-1]=1;
		
			}
			if(right==true){
			fix[(x)*m+y+1]=1;
			
			}
			if(up==true){	if(x+2<n){
				
			dfs2((x+2)*m+y);	
			}
			}
					if(right==true){	
			if(y+2<=m){
			dfs2((x)*m+y+2);
			}
					}
			if(left==true){	
			if(y-2>=0){
				
			dfs2((x)*m+y-2);
			}
			}
			if(down==true){	
				if(x-2>=0){
				dfs2((x-2)*m+y);
				}
			}
		}
		/*
		if(bruh<3){
			cout<<"No"<<endl;
			return 0;
			
		}*/
		
}
int main(){

	cin>>n>>m;	

	for(long long i=0; i<n; i++){
		for (long long j=0; j<m; j++){
			cin>>a[i*m+j];
			r[(i)*m+j]=0;
			fix[i*m+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*m+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( x>=n || x<0 || y<0 || y>=m){
					continue;
				}
				if(r[(i)*m+j]==1 && r[(x)*m+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)*m+j]=1;
					fix[(i+1)*m+j]=1;
					fix [(i-1)*m+j]=1;
					fix[(i)*m+j-1]=1;
					fix[(i)*m+j+1]=1;
					fix[(x)*m+y]=1;
					fix[(x+1)*m+y]=1;
					fix[(x-1)*m+y]=1;
					fix[(x)*m+y-1]=1;
					fix[(x)*m+y+1]=1;
				
				}
			}
			if(p>1){
				cout<<"No"<<endl;
				return 0;
			}
			
		}
	}

	
		for(long long i=0; i<k; i++){
			
		long long x=c[i].f,y=c[i].se;
		if(fix[(x)*m+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)*m+y]==1 || r[(x+1)*m+y]==1){
			bruh--;
			up=false;
		}
		if(x-1<0){
			bruh--;
			down=false;
		}else if(fix[(x-1)*m+y] || r[(x-1)*m+y]==1){
				bruh--;
				down=false;
		}
		if(y-1<0){
			bruh--;
			left=false;
		}else if(fix[(x)*m+y-1]==1 || r[(x)*m+y-1]==1){
			bruh--;
			left=false;
		}
		if( y+1>=m){
			bruh--;
			right=false;
		}else if(fix[(x)*m+y+1]==1 || r[(x)*m+y+1]==1){
				bruh--;
			right=false;
		}
		if(bruh==3){
			fix[(x)*m+y]=1;
			if(up==true){
			fix[(x+1)*m+y]=1;
		
			}
			if(down==true){
			fix[(x-1)*m+y]=1;
			
			}
			if(left==true){
			fix[(x)*m+y-1]=1;
		
			}
			if(right==true){
			fix[(x)*m+y+1]=1;
			
			}
			if(up==true){	if(x+2<n){
				
			dfs2((x+2)*m+y);	
			}
			}
					if(right==true){	
			if(y+2<=m){
			dfs2((x)*m+y+2);
			}
					}
			if(left==true){	
			if(y-2>=0){
				
			dfs2((x)*m+y-2);
			}
			}
			if(down==true){	
				if(x-2>=0){
				dfs2((x-2)*m+y);
				}
			}
		}
		if(bruh<3){
			cout<<"No";
			return 0;
		}
	
		if(bruh==4){
			r[(x)*m+y]=2;
		}
	}	
	
	for(long long i=0; i<n; i++){
		for(long long j=0; j<m; j++){
			if(r[(i)*m+j]!=2){
				continue;
			}
			if(i+2<n){
				if(r[(i+2)*m+j]==2){
					adj[i*m+j].pb((i+2)*m+j);
				}
			}
			if(i-2>=0){
				
				if(r[(i-2)*m+j]){
					adj[i*m+j].pb((i-2)*m+j);
				}
			}
			if(j+2<m){
				
				if(r[(i)*m+j+2]==2){
					adj[i*m+j].pb((i)*m+j+2);
				}
			}
			if(j-2>=0){
				
				if(r[(i)*m+j-2]==2){
					adj[i*m+j].pb((i)*m+j-2);
				}
			}
		}
	}
	for(long long i=0; i<n; i++){
		for(long long j=0; j<m; j++){
			if(fix[i*m+j]==0 && r[(i)*m+j]==2 ){
				dfs(i*m+j);
				if(size==3*nsize+1 && t.size()>0){
					pair<long long,pair<long long,long long> >  d=*t.begin();
				
					fix[(d.se.f)*m+d.se.se]=0;
				}
				if(size<3*nsize){
					cout<<"No"<<endl;
					return 0;
				}
				t.clear();
				nsize=0;
				size=0;
			}
		}
	}
	for(long long i=0; i<n; i++){
		for(long long j=0; j<m; j++){
			if(fix[i*m+j]==1 ){
				pas+=a[i*m+j];
			}
		}
	}
 
	cout<<pas;
}

Compilation message (stderr)

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

• 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