Submission #102450

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<set>

#define REP(i, b, n) for(int i = b; i <(int)n; i++)
#define rep(i, n) REP(i, 0, n)
#define FOR(it, o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++it)

using namespace std;


typedef long long ll;

const ll bx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const ll by[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const ll wx[4] = {0, 1, 0, -1};
const ll wy[4] = {-1, 0, 1, 0};

typedef long long P;

class DSINT{
public:
  vector<int> par, rank;;
  inline DSINT(int n){
    par = rank = vector<int>(n);
    rep(i, n){
      par[i] = i;
      rank [i] = 0;
    }
  }
  inline int find(int x){
    if(par[x] == x)return x;
    return par[x] = find(par[x]);
  }
  inline void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y)return;
    if(rank[x] < rank[y]){
      par[x] = y;
    }else{
      par[y] = x;
      if(rank[x] == rank[y])rank[x]++;
    }
  }
};
class DS{
public:
  map<P, P> v;
  map<P, int> rank;
  inline DS(){
    v.clear();
    rank.clear();
  }
  inline P find(P x){
    map<P, P>::iterator it = v.find(x);
    if(it == v.end()){
      return v[x] = x;
    }
    if(it->second == x)return x;
    P a= find(it->second);
    v.insert(it, make_pair(x, a));
    return a;
  }
  inline void unite(P x, P y){
    x = find(x);
    y = find(y);
    if(x == y)return;
    if(rank[x] < rank[y]){
      v[x] = y;
    }else{
      v[y] = x;
      if(rank[x] == rank[y])rank[x]++;
    }
  }
};
P bused[100000+10];
int n;

int solve(const vector<P> &V){
  vector<P> all;
  vector<P> id;
  rep(i, V.size()){
    rep(d, 8){
      P white = V[i] + (bx[d] << 32) + by[d];;
      if(binary_search(bused,bused+n, white))continue;
      all.push_back(white);
      rep(d2, 4){
	P white2 = white + (wx[d2] << 32) + wy[d2];;
	if(binary_search(bused,bused+n, white2))continue;
	all.push_back(white2);
      }
    }
  }
  
  sort(all.begin(), all.end());
  P pre = -1;
  int cnt = 0;
  rep(i, all.size()){
    if(all[i] != pre){
      id[i]= cnt++;
    }
    pre = all[i];
  }
  
  DSINT ds(cnt);
  set<P> setw;
  rep(i, V.size()){
    rep(d, 8){
      P white = V[i] + (bx[d] << 32) + by[d];;
      if(binary_search(bused,bused+n, white))continue;
      setw.insert(white);
      int w1 = id[lower_bound(all.begin(), all.end(), white) - all.begin()];
      rep(d2, 4){
	P white2 = white + (wx[d2] << 32) + wy[d2];;
	if (setw.count(white2) == 0) continue;
	if(binary_search(bused,bused+n, white2))continue;
	int w2 = id[lower_bound(all.begin(), all.end(), white2) - all.begin()];
	ds.unite(w1, w2);
      }
    }
  }

  set<P> ret;
  rep(i, V.size()){
    rep(d, 8){
      P white = V[i] + (bx[d] << 32) + by[d];;
      if(binary_search(bused,bused+n, white))continue;
      int w1 = id[lower_bound(all.begin(), all.end(), white) - all.begin()];
      ret.insert(ds.find(w1));
    }
  }
  return ret.size() -1;
}

P V[100000+10];


int main(){

  while(cin >> n){
    DS black;
    
    rep(i, n){
      ll x, y;
      scanf("%Ld %Ld", &x, &y);
      V[i] = (x<<32)+y;
      bused[i] = V[i];
    }
    sort(bused, bused+n);

    rep(i, n){
      rep(d, 8){
	P p = V[i] + (bx[d] << 32) + by[d];

	if(!binary_search(bused, bused+n, p))continue;

	black.unite(V[i], p);
      }
    }
    
    //black sets
    map<P, vector<P> > M;
    rep(i, n){
      M[black.find(V[i])].push_back(V[i]);
    }
    
    int ans = 0;
    FOR(it, M){
      if(it->second.size() <=3)continue;
      ans += solve(it->second);
    }
    printf("%d\n", ans);
  }
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:149:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result