結果

問題 No.421 しろくろチョコレート
ユーザー algon_320algon_320
提出日時 2016-09-10 00:04:41
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,518 bytes
コンパイル時間 1,818 ms
コンパイル使用メモリ 179,748 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-28 06:03:24
合計ジャッジ時間 3,390 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 WA -
testcase_02 AC 2 ms
6,944 KB
testcase_03 WA -
testcase_04 AC 2 ms
6,944 KB
testcase_05 WA -
testcase_06 AC 2 ms
6,940 KB
testcase_07 WA -
testcase_08 AC 2 ms
6,940 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 2 ms
6,940 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 WA -
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 WA -
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 3 ms
5,376 KB
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 WA -
testcase_43 WA -
testcase_44 AC 2 ms
5,376 KB
testcase_45 WA -
testcase_46 AC 2 ms
5,376 KB
testcase_47 WA -
testcase_48 AC 2 ms
5,376 KB
testcase_49 WA -
testcase_50 WA -
testcase_51 AC 3 ms
5,376 KB
testcase_52 WA -
testcase_53 AC 2 ms
5,376 KB
testcase_54 AC 2 ms
5,376 KB
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 WA -
testcase_61 WA -
testcase_62 AC 2 ms
5,376 KB
testcase_63 AC 2 ms
5,376 KB
testcase_64 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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