結果

問題 No.421 しろくろチョコレート
ユーザー algon_320
提出日時 2016-09-10 00:04:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,518 bytes
コンパイル時間 1,839 ms
コンパイル使用メモリ 179,668 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-16 18:49:07
合計ジャッジ時間 3,461 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32 WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
typedef pair<int,int> pii;
#define ITR(v,c) for(auto v=begin(c);v!=end(c);v++)
#define FOR(v,a,n) for(int v=a;v<(int)(n);v++)
#define FORE(x,arr) for(auto &x:arr)
#define REP(v,n) FOR(v,0,n)
#define RREP(v,n) for(int v=(int)(n);v>=0;v--)
#define ALL(c) begin(c),end(c)
const int DX[4]={0,1,0,-1}, DY[4]={-1,0,1,0};
const int INF = 1e9;
const ll INFLL = 1e18;
template<class T,class U>ostream&operator<<(ostream &os,const pair<T,U> &p){
    os<<"("<<p.first<<","<<p.second<<")";return os;}
template<class T>ostream&operator<<(ostream &os,const vector<T> &v){
    ITR(i,v)os<<*i<<(i==end(v)-1?"":"\n");return os;}
//------------------------------------------------------------------------------

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
	    x = root(x); y = root(y);
        if(x != y) {
            if(data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
	}
	bool findSet(int x, int y) {
	    return root(x) == root(y);
    }
	int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

int h,w;
inline int getIndex(int x,int y) {
    return x+y*w;
}
signed main() {
    cin>>h>>w;
    vector<string> s(h);
    map<int,pii> blocks;
    UnionFind uf(h*w);
    REP(i,h) cin>>s[i];

    REP(i,h) {
        REP(j,w) {
            if(s[i][j]!='.') {
                if(i!=0 && s[i-1][j]!='.') uf.unionSet(getIndex(j,i-1),getIndex(j,i));
                if(j!=0 && s[i][j-1]!='.') uf.unionSet(getIndex(j-1,i),getIndex(j,i));
            }
        }
    }

    REP(i,h) {
        REP(j,w) {
            int root = uf.root(getIndex(j,i));
            if(blocks.find(root)==blocks.end()) {
                blocks[root] = pii(s[i][j]=='w',s[i][j]=='b');
            }
            else {
                blocks[root].first += (s[i][j]=='w');
                blocks[root].second += (s[i][j]=='b');
            }
        }
    }

    int ans=0;
    int white=0,black=0;
    ITR(i,blocks) {
        int w = i->second.first;
        int b = i->second.second;
        if(w<=b) {
            ans+=w*100;
            black+=b-w;
        }
        else {
            ans+=b*100;
            white+=w-b;
        }
    }
    ans+=min(white,black)*10;
    ans+=max(white,black)-min(white,black);
    cout<<ans<<endl;
    return 0;
}
0