Submission #6067975


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];
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 < 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(vec[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 1438 Byte
Status WA
Exec Time 94 ms
Memory 16512 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 4
WA × 16
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 AC 5 ms 8832 KB
02.txt WA 5 ms 8832 KB
03.txt WA 5 ms 8832 KB
04.txt WA 5 ms 8960 KB
05.txt WA 5 ms 8832 KB
06.txt WA 6 ms 8960 KB
07.txt WA 6 ms 8960 KB
08.txt WA 6 ms 8960 KB
09.txt WA 90 ms 15744 KB
10.txt WA 90 ms 15872 KB
11.txt WA 90 ms 15744 KB
12.txt WA 91 ms 16512 KB
13.txt WA 91 ms 16512 KB
14.txt WA 94 ms 15872 KB
15.txt WA 92 ms 15872 KB
16.txt WA 92 ms 15872 KB
17.txt WA 68 ms 11136 KB
s1.txt AC 5 ms 8832 KB
s2.txt AC 5 ms 8832 KB
s3.txt AC 5 ms 8832 KB