AtCoder Beginner Contest #131 F問題 - Must Be Rectangular!

Source

AtCoder Beginner Contest #131
問題文

問題概要

省略

解法

省略

cLay（version 20190706-1）のコード

C++に変換後のコードはこちら

int N, X[1d5], Y[1d5];
int xs[2d5], ys[2d5];
{
  int i;
  ll res;
  unionFind uf;
  
  rd(N,(X--,Y--)(N));
  rep(i,N) Y[i] += 1d5;
  uf.malloc(2d5);
  uf.init(2d5);

  res = N;
  rep(i,N) uf(X[i], Y[i]);

  sortA(N, X, Y);
  rep(i,1,N) if(X[i]==X[i-1]) uf(Y[i], Y[i-1]);
  sortA(N, Y, X);
  rep(i,1,N) if(Y[i]==Y[i-1]) uf(X[i], X[i-1]);

  rep(i,1d5) xs[uf(i)]++;
  rep(i,1d5) ys[uf(i+1d5)]++;

  res = -N;
  rep(i,2d5) res += (ll) xs[i] * ys[i];

  wt(res);
}

Current time: 2024年04月24日21時58分57秒
Last modified: 2019年07月06日23時23分23秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC131 ABC_F
トップページに戻る

Logged in as: unknown user (not login)

ログイン：