首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。