Submission #654595

#	Time	Username	Problem	Language	Result	Execution time	Memory
654595		Mohammad_Parsa	T-Covering (eJOI19_covering)	C++14	100 / 100	138 ms	57572 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
#define int long long
 
const int N=2e3+7;
int mn,t,M,ty,x[N*N],y[N*N];
vector<int> z[N],a[N],b[N],yek[N],vis[N];
int dx[4]={-2,2,0,0},xd[4]={-1,1,0,0};
int dy[4]={0,0,-2,2},yd[4]={0,0,-1,1};
 
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];
    b[x][y]=1;
    for(int i=0;i<4;i++){
        int p=x+dx[i],q=y+dy[i];
        if(p>=0 && q>=0 && z[p][q]){
			t++;
			if(!vis[p][q]) dfs(p,q);
		}
		if(x+xd[i]>=0 && y+yd[i]>=0) mn=min(mn,a[x+xd[i]][y+yd[i]]),b[x+xd[i]][y+yd[i]]=1;
    }
}
 
int32_t main(){
    ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
	int g=0;
	if(n>m) g=1,swap(n,m);
	for(int i=0;i<=n+5;i++){
		a[i].resize(m+5);
		b[i].resize(m+5);
		z[i].resize(m+5);
		vis[i].resize(m+5);
		yek[i].resize(m+5);
		for(int j=0;j<m+5;j++){
			a[i][j]=1007;
		}
	}
	if(g) swap(n,m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
			if(g) swap(i,j);
            cin>>a[i][j];
			if(g) swap(i,j);
        }
    }
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        cin>>x[i]>>y[i];x[i]++;y[i]++;
		if(g) swap(x[i],y[i]);
        z[x[i]][y[i]]=1;
    }
    if(g) swap(n,m);
    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;
    
    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;
        }
    }
 
 
    for(int i=0;i<k;i++){
        if(!vis[x[i]][y[i]]){
            mn=1e9;t=0;M=0;ty=0;
            dfs(x[i],y[i]);
            t/=2;
            //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(n==1 || m==1) f=1;
 
    if(f){
        cout<<"No";
        return 0;
    }
    cout<<ans;
}

• 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