結果

問題 No.348 カゴメカゴメ
ユーザー rickythetarickytheta
提出日時 2016-02-26 23:29:56
言語 C++11
(gcc 13.3.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,897 bytes
コンパイル時間 1,358 ms
コンパイル使用メモリ 165,496 KB
実行使用メモリ 74,936 KB
最終ジャッジ日時 2024-09-23 02:19:24
合計ジャッジ時間 4,476 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 39 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef complex<double> P;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()
#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD
int n,m;
int mp[1252][1252];
int po[1252][1252];
int vx[8] = {1,0,-1,0,1,1,-1,-1};
int vy[8] = {0,1,0,-1,1,-1,-1,1};
int dfs(int a,int b,int id){
if(a<0 || a>=n || b<0 || b>=m)return 0;
if(mp[a][b] >= 0)return 0;
mp[a][b] = id;
int res = 1;
REP(i,8){
res += dfs(a+vx[i],b+vy[i],id);
}
return res;
}
void dfs2(int a,int b,int par){
if(a<0 || a>=n || b<0 || b>=m)return;
if(mp[a][b] == -1)return;
if(mp[a][b] > 0){
po[a][b] = par;
if(mp[a][b]!=par)return;
}
mp[a][b] = -1;
REP(i,4) dfs2(a+vx[i],b+vy[i],par);
}
struct node{
int val;
vector<node*> ch;
node(int v):val(v){
ch = vector<node*>();
}
void addch(node* n){
ch.push_back(n);
}
};
node* yey[125252];
// first: 使max
// second: 使max
pii dfs3(node* a){
pii ret;
int cnt = a->ch.size();
pii sum;
REP(i,cnt){
pii rec = dfs3(a->ch[i]);
sum.first += rec.first;
sum.second += rec.second;
}
ret.first = a->val + sum.second;
ret.second = max(sum.first, sum.second);
return ret;
}
int main(){
cin>>n>>m;
n+=2;
m+=2;
REP(i,n){
string s;
if(i==0 || i==n-1){
s = string(m,'.');
}else{
cin>>s;
s = '.' + s + '.';
}
REP(j,m){
mp[i][j] = (s[j]=='x'?-1:0);
}
}
// grouping
int wawa[125252];
int iter = 1;
REP(i,n)REP(j,m){
if(mp[i][j]>=0)continue;
wawa[iter] = dfs(i,j,iter);
iter++;
}
iter--;
// iter
//
int left=0, top=0, right=n-1, bottom=m-1;
int root = 125222;
yey[root] = new node(0);
dfs2(0,0,root);
while(true){
bool flag = false;
int nl,nt,nr,nb;
nl=right;
nt=bottom;
nr=left;
nb=top;
FOR(i,left,right+1)FOR(j,top,bottom+1){
if(mp[i][j]<=0)continue;
nl=min<int>(nl,i);
nr=max<int>(nr,i);
nt=min<int>(nt,j);
nb=min<int>(nb,j);
int id = mp[i][j];
yey[id] = new node(wawa[id]);
yey[po[i][j]]->addch(yey[id]);
dfs2(i,j,id);
flag = true;
}
if(!flag)break;
left=nl;
right=nr;
top=nt;
bottom=nb;
}
//
int res = 0;
REP(i,(yey[root]->ch).size()){
node* to = (yey[root]->ch)[i];
pii x = dfs3(to);
res += max(x.first,x.second);
}
cout<<res<<endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0