Submission #6069126


Source Code Expand

Copy
#include <iostream>
#include <string>
#include <stdlib.h>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
#include <map>
#define llint long long

using namespace std;
typedef pair<llint, llint> P;

struct UnionFind{
	int size;
	vector<int> parent;
	
	UnionFind(){}
	UnionFind(int size){
		this->size = size;
		parent.resize(size+1);
		init();
	}
	void init(){
		for(int i = 0; i <= size; i++) parent[i] = i;
	}
	int root(int i){
		if(parent[i] == i) return i;
		return parent[i] = root(parent[i]);
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
	void unite(int i, int j){
		int root_i = root(i), root_j = root(j);
		if(root_i == root_j) return;
		parent[root_i] = root_j;
	}
};

llint n;
llint x[100005], y[100005];
UnionFind uf(100005);
vector<llint> vec[100005], vecx[100005];
set<llint> S[100005];
llint cnt[100005];

int main(void)
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];
	
	for(int i = 1; i <= n; i++) vec[x[i]].push_back(y[i]);
	for(int i = 1; i <= n; i++) vecx[y[i]].push_back(x[i]);
	
	for(int i = 1; i < 100005; i++){
		for(int j = 1; j < vec[i].size(); j++) uf.unite(vec[i][j-1], vec[i][j]);
	}
	for(int i = 1; i < 100005; i++){
		for(int j = 0; j < vec[i].size(); j++){
			S[uf.root(i)].insert(vecx[i][j]);
		}
		cnt[uf.root(i)]++;
	}
	
	llint ans = 0;
	for(int i = 1; i < 100005; i++){
		ans += S[i].size() * cnt[i];
	}
	ans -= n;
	cout << ans << endl;
	
	return 0;
}

Submission Info

Submission Time
Task F - Must Be Rectangular!
User leaf1415
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1514 Byte
Status RE
Exec Time 172 ms
Memory 15232 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 2
WA × 1
AC × 2
WA × 1
RE × 17
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 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 RE 127 ms 10752 KB
02.txt RE 100 ms 10112 KB
03.txt RE 100 ms 10112 KB
04.txt RE 100 ms 10112 KB
05.txt RE 100 ms 10112 KB
06.txt RE 101 ms 10112 KB
07.txt RE 100 ms 10112 KB
08.txt RE 101 ms 10112 KB
09.txt RE 168 ms 14720 KB
10.txt RE 172 ms 15232 KB
11.txt RE 169 ms 15232 KB
12.txt RE 170 ms 15232 KB
13.txt RE 170 ms 15232 KB
14.txt RE 169 ms 15232 KB
15.txt RE 171 ms 15232 KB
16.txt RE 168 ms 15232 KB
17.txt RE 158 ms 13568 KB
s1.txt WA 5 ms 10880 KB
s2.txt AC 5 ms 10880 KB
s3.txt AC 5 ms 10880 KB