제출 #498493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498493		uncripted	T-Covering (eJOI19_covering)	C++11	15 / 100	53 ms	96452 KiB

covering

#include<bits/stdc++.h>
#define f first
#define se second
#define pb push_back
using namespace std;
 
int ss=0;
int size=0;
multiset<int> t;
int nsize=0;
	int a[2000][2000];	
	int r[2000][2000];
	int fix[2000][2000];
	int gr[2000][2000];
	int vis[2000][2000];
	
	vector<pair<int,int> > adj[2000][2000];
void dfs(pair<int,int> 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(int 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(){
	int n,m;
	cin>>n>>m;
 
	for(int i=0; i<n; i++){
		for (int 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;
		}
	}
	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][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(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][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][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(int i=0; i<n; i++){
		for(int 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(int i=0; i<n; i++){
		for(int 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(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(fix[i][j]==1 || vis[i][j]==1){
				pas+=a[i][j];
			}
		}
	}
 
	cout<<pas-ss;
}

컴파일 시 표준 에러 (stderr) 메시지

covering.cpp: In function 'void dfs(std::pair<int, int>)':
covering.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int 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: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30