Submission #654195

#	Time	Username	Problem	Language	Result	Execution time	Memory
654195		Mohammad_Parsa	T-Covering (eJOI19_covering)	C++14	25 / 100	75 ms	36928 KiB

covering

/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
#define F first
#define S second
#define mk make_pair
 
const int N=1e3+7;
int mn,t,M,ty,z[N][N],a[N][N],b[N][N],vis[N][N],x[N*N],y[N*N],r[N*N],c[N*N],yek[N][N];
vector<pair<int,int>> vec[N][N];
 
int sumz(int x,int y){
	int ans=0;
	for(int i=-1;i<=1;i++)
		for(int j=-1;j<=1;j++)
			ans+=z[x+i][y+j];
	return ans;
}
 
void dfs(int x,int y){
	vis[x][y]=1;M++;ty+=yek[x][y];
	mn=min(mn,min(a[x][y+1],min(a[x][y-1],min(a[x+1][y],a[x-1][y]))));
	b[x][y]=1,b[x-1][y]=1,b[x+1][y]=1,b[x][y-1]=1,b[x][y+1]=1;
	for(auto u:vec[x][y]){
		int p=u.F,q=u.S;
		if(vis[p][q]) t++;
		else dfs(p,q);
	}
}
 
int main(){
	ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<N;i++) fill(a[i],a[i]+N,1000+7);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	int k;
	cin>>k;
	for(int i=0;i<k;i++){
		cin>>x[i]>>y[i];x[i]++;y[i]++;
		z[x[i]][y[i]]=1;
	}
	int f=0;
	for(int i=0;i<k;i++){
		if((x[i]==1 && y[i]==1) || (x[i]==n && y[i]==1) || (x[i]==1 && y[i]==m) || (x[i]==n && y[i]==m)){
			if(sumz(x[i],y[i])>0) f=1;
		}
		else if(x[i]==1 || x[i]==n || y[i]==1 || y[i]==m){
			if(sumz(x[i],y[i])>1) f=1;
		}
		else{
			if(sumz(x[i],y[i])>2) f=1;
		}
	}	
	
	int ans=0,h=0;
	for(int i=0;i<k;i++){
		int p=x[i],q=y[i];
		if(p==1 || p==n || q==1 || q==m){
			b[p][q]=b[p-1][q]=b[p+1][q]=b[p][q-1]=b[p][q+1]=1;
			yek[p][q]=1;
		}
		else if(sumz(p,q)==2){
			b[p][q]=b[p-1][q]=b[p+1][q]=b[p][q-1]=b[p][q+1]=1;
			yek[p][q]=1;
		}
		else{
			r[h]=p,c[h]=q,h++;	
		}
	}
	//for(int i=0;i<k;i++) z[x[i]][y[i]]=0;
	for(int i=0;i<h;i++) z[r[i]][c[i]]=1;
 
 
	for(int i=0;i<k;i++){
		int p=r[i],q=c[i];
		if(z[p+2][q]==1) vec[p][q].pb(mk(p+2,q));
		if(z[p-2][q]==1) vec[p][q].pb(mk(p-2,q));
		if(z[p][q+2]==1) vec[p][q].pb(mk(p,q+2));
		if(z[p][q-2]==1) vec[p][q].pb(mk(p,q-2));
	}
	for(int i=0;i<k;i++){
		if(!vis[r[i]][c[i]]){
			mn=1e9;t=0;M=0;ty=0;
			dfs(r[i],c[i]);
			//cout<<M<<" "<<t<<endl;
			if(ty>1) f=1;
			if(t>M) f=1;
			if(t==M && ty==1) f=1;
			if(t==M-1 && ty==0) ans-=mn;
		}
	}
 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ans+=b[i][j]*a[i][j];
		}
	}
	
	if(f){
		cout<<"No";
		return 0;
	}
	cout<<ans;
}

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