Submission #3986685


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct UnionFind{
  vector<int> data;
  UnionFind(int n) : data(n, -1) {}
  bool unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return false;
    if(data[y] < data[x]) swap(x,y);
    data[x] += data[y];
    data[y] = x;
    return x != y;
  }
  bool same(int x, int y){ return find(x) == find(y); }
  int find(int x){
    if(data[x] < 0) return x;
    return data[x] = find(data[x]);
  }
};

bool in_range(int a, int b){
  return a >= 0 && a < b;
}

int main(){
  int H, W;
  cin >> H >> W;
  vector<string> S(H);
  int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
  for(int i = 0; i < H; ++i) cin >> S[i];
  UnionFind uf(H*W);
  for(int i = 0; i < H; ++i){
    for(int j = 0; j < W; ++j){
      for(int k = 0; k < 4; ++k){
        int i_ = i + dx[k], j_ = j + dy[k];
        if(in_range(i_,H) and in_range(j_,W) and S[i][j] != S[i_][j_]){
          uf.unite(i*W+j,i_*W+j_);
        }
      }
    }
  }
  long long ans = 0;
  map<int,pair<int,int> > M;
  for(int i = 0; i < H*W; ++i){
    if(S[i/W][i%W] == '#') ++M[uf.find(i)].first;
    else ++M[uf.find(i)].second;
  }
  for(auto e : M){
    ans += (long long)(e.second.first)*e.second.second;
  }
  cout << ans << endl;
}

Submission Info

Submission Time
Task C - Alternating Path
User TAB
Language C++ (GCC 5.4.1)
Score 0
Code Size 1323 Byte
Status

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:52:12: error: ‘e’ does not name a type
   for(auto e : M){
            ^
./Main.cpp:55:3: error: expected ‘;’ before ‘cout’
   cout << ans << endl;
   ^
./Main.cpp:56:1: error: expected primary-expression before ‘}’ token
 }
 ^
./Main.cpp:56:1: error: expected ‘)’ before ‘}’ token
./Main.cpp:56:1: error: expected primary-expression before ‘}’ token