首页 > 代码库 > CodeForces 659F Polycarp and Hay

CodeForces 659F Polycarp and Hay

 

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c=getchar(); x=0;    while(!isdigit(c)) c=getchar();    while(isdigit(c)) {x=x*10+c-0; c=getchar();}}const int maxn=1010;int n,m,sz,c; LL k;struct X { int r,c; LL v; }s[maxn*maxn];int fa[maxn*maxn],a[maxn][maxn],cnt[maxn*maxn]; LL ans[maxn][maxn];bool f[maxn][maxn],q;int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};int Find(int x){    if(x!=fa[x]) fa[x]=Find(fa[x]);    return fa[x];}bool cmp(X a,X b) { return a.v<b.v; }void work(int a,int b){    if(b<0||b>=n*m) return;    int fx=Find(a),fy=Find(b);    if(f[b/m][b%m]==0) return;    if(fx==fy) return;    fa[fy]=fx;    cnt[fx]=cnt[fx]+cnt[fy]; cnt[fy]=0;}bool check(int a,int b){    if(a>=0&&a<n&&b>=0&&b<m) return 1;    return 0;}void dfs(int x,int y,LL v,int f){    c++; ans[x][y]=v; if(c>=f) return;    for(int i=0;i<4;i++)    {        int tx=x+dir[i][0],ty=y+dir[i][1];        if(!check(tx,ty)) continue;        if(a[tx][ty]<v) continue;        if(ans[tx][ty]!=0) continue;        dfs(tx,ty,v,f); if(c>=f) return;    }}int main(){    scanf("%d%d%lld",&n,&m,&k);    for(int i=0;i<n*m;i++) fa[i]=i,cnt[i]=1;    for(int i=0;i<n;i++)    {        for(int j=0;j<m;j++)        {            scanf("%lld",&a[i][j]);            s[sz].r=i; s[sz].c=j; s[sz].v=a[i][j]; sz++;        }    }    sort(s,s+sz,cmp);    for(int j=sz-1; j>=0; j--)    {        int id1=s[j].r*m+s[j].c,id2;        if(check(s[j].r-1,s[j].c))        {            id2=(s[j].r-1)*m+s[j].c;            work(id1,id2);        }        if(check(s[j].r+1,s[j].c))        {            id2=(s[j].r+1)*m+s[j].c;            work(id1,id2);        }        if(check(s[j].r,s[j].c-1))        {            id2=s[j].r*m+s[j].c-1;            work(id1,id2);        }        if(check(s[j].r,s[j].c+1))        {            id2=s[j].r*m+s[j].c+1;            work(id1,id2);        }        f[s[j].r][s[j].c]=1;        int d=Find(id1);        if(k%s[j].v==0&&(LL)cnt[d]>=k/s[j].v)        {            dfs(s[j].r,s[j].c,s[j].v,(int)(k/s[j].v));            q=1; break;        }        if(q) break;    }    if(!q) { printf("NO\n"); return 0;}    printf("YES\n");    for(int i=0;i<n;i++)    {        for(int j=0;j<m;j++)        {            printf("%lld",ans[i][j]);            printf(" ");        }       printf("\n");    }    return 0;}

 

CodeForces 659F Polycarp and Hay