Submission #6110765


Source Code Expand

Copy
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#define rep(i,x,y) for(ll i=(x); i<(y); i++)

using namespace std;
typedef long long int ll;
typedef pair<ll,ll> PLL;

const ll V = 1000000; // 片方の頂点の最大数
vector<ll> to[2 * V]; // xあるいはyからつながっている先。y側はVの下駄を履かせる
bool visited[2 * V];
vector<ll> cnt;

void dfs(int v) {
  if (visited[v])
    return;
  visited[v] = true;
  cnt[v/V]++;
  for (ll u : to[v]) {
    dfs(u);
  }
}

signed main(void) {
  // (x,y)座標を二部グラフにする
  ll N;
  cin>>N;
  rep(i,0,N) {
    ll x, y;
    cin>>x>>y;
    y += V;
    to[x].push_back(y);
    to[y].push_back(x);
  }

  ll ans = 0;
  rep(i,0,2*V){
    if (visited[i])
      continue;
    cnt = vector<ll>(2);
    dfs(i);
    ans += cnt[0]*cnt[1];
  } 
  ans -= N;
  cout<<ans<<endl;
  return 0;
}

Submission Info

Submission Time
Task F - Must Be Rectangular!
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1137 Byte
Status
Exec Time 171 ms
Memory 54144 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 600 / 600 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 83 ms 49024 KB
02.txt 84 ms 49024 KB
03.txt 83 ms 49024 KB
04.txt 83 ms 49024 KB
05.txt 84 ms 49024 KB
06.txt 84 ms 49152 KB
07.txt 84 ms 49152 KB
08.txt 85 ms 49152 KB
09.txt 160 ms 54144 KB
10.txt 160 ms 52736 KB
11.txt 161 ms 52736 KB
12.txt 161 ms 52736 KB
13.txt 171 ms 52736 KB
14.txt 162 ms 52736 KB
15.txt 160 ms 52736 KB
16.txt 163 ms 52736 KB
17.txt 141 ms 51072 KB
s1.txt 84 ms 49024 KB
s2.txt 84 ms 49024 KB
s3.txt 84 ms 49024 KB