fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define foru(i,a,b) for(int i=(a); i<=(b); ++i)
  5. #define ford(i,a,b) for(int i=(a); i>=(b); --i)
  6. #define rep(i,a) for(int i=0; i<(a); ++i)
  7. #define sz(a) (int)(a).size()
  8. #define all(a) (a).begin(),(a).end()
  9. #define bit(s,i) (((s)>>(i))&1)
  10. #define ii pair<int,int>
  11. #define fi first
  12. #define se second
  13. #define pb push_back
  14. #define eb emplace_back
  15. #define ll long long
  16. #define _ << " " <<
  17.  
  18. template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
  19. template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}
  20.  
  21. const int N=2e5+5;
  22.  
  23. int dx[]={0,0,1,-1};
  24. int dy[]={1,-1,0,0};
  25.  
  26. int n,m,par[N],deg[N],ans[N],sz[N]; bool vis[N];
  27. ii d[N];
  28. vector<int> adj[N];
  29.  
  30. int id(int x, int y){
  31.     return x*m+y;
  32. }
  33.  
  34. bool inBoard(int x, int y){
  35.     return x>=0 && y>=0 && x<n && y<m;
  36. }
  37.  
  38. void pre(int u){
  39.     sz[u]=1;
  40.     for(int v:adj[u]){
  41.         pre(v);
  42.         sz[u]+=sz[v];
  43.     }
  44. }
  45.  
  46. void dfs(int u, int out){
  47.     ans[u]=min(d[u].fi, out+sz[u]);
  48.     for(int v:adj[u]){
  49.         dfs(v, min(d[u].fi, out+sz[u]-sz[v]));
  50.     }
  51. }
  52.  
  53. int find(int x){
  54.     return par[x]==x ? x : par[x]=find(par[x]);
  55. }
  56.  
  57. void solve(){
  58.     cin>>n>>m;
  59.     rep(i,n*m) cin>>d[i].fi;
  60.     rep(i,n*m) d[i].se=i, par[i]=i;
  61.  
  62.     sort(d, d+n*m, greater<ii>());
  63.     rep(i,n*m){
  64.         int ix=d[i].se/m, iy=d[i].se%m;
  65.         rep(k,4){
  66.             int jx=ix+dx[k], jy=iy+dy[k];
  67.             if(!inBoard(jx,jy)) continue;
  68.  
  69.             int j=id(jx,jy);
  70.             if(!vis[j]) continue;
  71.  
  72.             int ip=find(d[i].se), jp=find(j);
  73.             if(ip==jp) continue;
  74.  
  75.             par[jp]=ip;
  76.             adj[ip].eb(jp);
  77. //            cout<<ip _ jp<<'\n';
  78.             ++deg[jp];
  79.         }
  80.         vis[d[i].se]=true;
  81.     }
  82.  
  83.     int rt=0;
  84.     rep(i,n*m) if(deg[i]==0) rt=i;
  85.  
  86.     sort(d, d+n*m, [] (ii x, ii y){return x.se<y.se;});
  87.  
  88.     pre(rt);
  89.     dfs(rt,0);
  90.  
  91.     int res=0;
  92.     rep(i,n*m){
  93.         int ix=i/m, iy=i%m;
  94.         if(ix==0||iy==0||ix==n-1||iy==m-1) maxi(res,ans[i]);//,cout<<ans[i] _ i _ d[i].fi<<'\n';
  95.     }
  96.     cout<<res<<'\n';
  97. }
  98.  
  99. int32_t main(){
  100.     #define task "test"
  101.     if(fopen(task".inp","r")){
  102.         freopen(task".inp","r",stdin);
  103.         freopen(task".out","w",stdout);
  104.     }
  105.     cin.tie(0)->sync_with_stdio(0);
  106.  
  107.     int tc=1; //cin>>tc;
  108.     rep(i,tc){
  109.         solve();
  110.     }
  111. }
  112.  
Success #stdin #stdout 0.01s 12064KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/0xvLnb
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!