結果

問題 No.348 カゴメカゴメ
コンテスト
ユーザー nmnmnmnmnmnmnm
提出日時 2016-02-27 00:52:39
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 3,708 bytes
コンパイル時間 1,330 ms
コンパイル使用メモリ 116,968 KB
実行使用メモリ 50,224 KB
最終ジャッジ日時 2024-09-24 10:51:50
合計ジャッジ時間 8,068 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 52
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int f(int, int, int)’:
main.cpp:101:1: warning: no return statement in function returning non-void [-Wreturn-type]
  101 | }
      | ^

ソースコード

diff # 

#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
 
#define MOD 1000000007

int h,w;

int d[1005][1005];

vector<int> uf, usz;
int nc;

void init(int n){
  vector<int> uf_(n);
  vector<int> usz_(n, 1);
  uf = uf_;
  usz = usz_;
  nc = n;

  for(int i = 0; i < uf.size(); i++){
    uf[i] = i;
  }
}

int find(int a){
  return (uf[a] == a) ? a : uf[a] = find(uf[a]);
}

void union_(int a, int b){
  a = find(a);
  b = find(b);

  if(a != b){
    if(usz[a] >= usz[b]){
      swap(a, b);
    }
    uf[a] = b;
    usz[b] += usz[a];
    nc--;
  }
}

int check(int a, int b){
  return (find(a) == find(b)) ? 1 : 0;
}

int get_size(int a){
  return usz[find(a)];
}

int dd[1005][1005];
int d1[1005][1005];

int f(int a,int py,int px){
  int dy[4] = {-1,0,0,1};
  int dx[4] = {0,-1,1,0};
  dd[py][px]=1;
  rep(i,0,4){
    if(py+dy[i]<0)continue;
    if(py+dy[i]>=h)continue;
    if(px+dx[i]<0)continue;
    if(px+dx[i]>=w)continue;
    if(d[py+dy[i]][px+dx[i]]!=0){
      d1[a][d[py+dy[i]][px+dx[i]]]=1;
      d1[d[py+dy[i]][px+dx[i]]][a]=1;
      continue;
    }
    if(dd[py+dy[i]][px+dx[i]]==1){
      continue;
    }
    f(a,py+dy[i],px+dx[i]);
  }
}

vector<vector<int> > vg;
vector<int> vc;
int dp[2][1000005];
int f2(int p, int flag){
  if(dp[flag][p]!=-1){
    return dp[flag][p];
  }
  if(flag == 0){
    int ret = 0;
    rep(i,0,vg[p].sz){
      ret += max(f2(vg[p][i],0),f2(vg[p][i],1));
    }
    return dp[0][p] = ret;
  }
  else{
    int ret = vc[p];
    rep(i,0,vg[p].sz){
      ret += f2(vg[p][i],0);
    }
    return dp[1][p] = ret;
  }
}

int main(){
  cin>>h>>w;
  if(h==1||w==1){
    cout << 0 << endl;
    return 0;
  }
  vector<string> vs;
  rep(i,0,h){
    string s;
    cin>>s;
    vs.pb(s);
  }
  clr(d,0);
  rep(y,0,h){
    rep(x,0,w){
      if(vs[y][x]=='x'){
        d[y+1][x+1] = 1;
      }
    }
  }
  h+=2;
  w+=2;
  init(h*w);
  rep(y,1,h-1){
    rep(x,1,w-1){
      int dx[8]={-1,0,1,-1,1,-1,0,1};
      int dy[8]={-1,-1,-1,0,0,1,1,1};
      rep(i,0,8){
        if(d[y][x]==1&&d[y+dy[i]][x+dx[i]]==1){
          union_(w*y+x,w*(y+dy[i])+x+dx[i]);
        }
      }
    }
  }
  set<int> se;
  rep(y,0,h){
    rep(x,0,w){
      if(d[y][x]==1){
        int a = find(w*y+x);
        d[y][x]=a;
        se.insert(a);
      }
    }
  }
  vector<int> vv(all(se));
  map<int,int> ma;
  rep(i,0,vv.sz){
    ma[vv[i]]=i+1;
  }
  rep(y,0,h){
    rep(x,0,w){
      if(d[y][x]!=0){
        d[y][x] = ma[d[y][x]];
      }
    }
  }
  int nn = vv.sz;

  vector<int> vc_(nn+1,0);
  vc = vc_;
  vector<int> vy1(nn+1);
  vector<int> vx1(nn+1);
  vc[0] = 0;
  vy1[0] = 0;
  vx1[0] = 0;
  rep(y,0,h){
    rep(x,0,w){
      if(d[y][x]!=0){
        vy1[d[y][x]] = y;
        vx1[d[y][x]] = x;
        vc[d[y][x]]++;
      }
    }
  }
  vector<vector<int> > vp(nn+1,vector<int>());
  clr(d1,0);
  rep(i,0,nn+1){
    clr(dd,0);
    f(i,vy1[i],vx1[i]);
  }
  vector<int> vb(nn+1,0);
  vb[0] = 1;
  vector<vector<int> > vg_(nn+1,vector<int>());
  vg = vg_;
  rep(i,0,nn+1){
    rep(j,i+1,nn+1){
      if(d1[i][j]==1){
        if(vb[j]==0){
          vb[j]=1;
          vg[i].pb(j);
        }
      }
    }
  }
  clr(dp,-1);
  cout << f2(0,0) << endl;
  return 0;
}
0