Submission #498550

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

covering

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

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

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

	}
	t.insert({a[(x+1)*n+(y)],{x+1,y}});	
		t.insert({a[(x)*n+(y-1)],{x,y-1}});	

			t.insert({a[(x)*n+(y+1)],{x,y+1}});
	t.insert({a[(x-1)*n+(y)], {x-1,y}});
	fix[(x-1)*n+(y)]=1;
	fix[(x+1)*n+(y)]=1;
	fix[(x)*n+(y-1)]=1;
	fix[(x)*n+(y+1)]=1;
	for(int i=0; i<adj[p].size(); i++){
		
		if(fix[adj[p][i]]==1){
			continue;
		}
		dfs(adj[p][i]);
	}
}
int main(){

	cin>>n>>m;	
	int r[n][m];

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

Compilation message (stderr)

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