Submission #101946

---

Source Code Expand

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int N;
int X[100000], Y[100000];
vector<int> Xs, Ys;

vector<int> Ycor[200002];
vector<pair<int, int> > ranges[200002]; //slice with X
vector<int> idxs[200002];

int uf[5000000];

int root(int p){
	return (uf[p] < 0) ? p : (uf[p] = root(uf[p]));
}

void join(int p, int q)
{
	p = root(p);
	q = root(q);
	if(p==q) return;
	uf[p] += uf[q];
	uf[q] = p;
}

bool intersect(pair<int, int> x, pair<int, int> y)
{
	return !(x.second <= y.first || y.second <= x.first);
}

void unify(int p, int q)
{
	int ip=0, iq=0;
	pair<int, int> r1, r2;

	for(;ip<ranges[p].size()&&iq<ranges[q].size();){
		r1 = ranges[p][ip];
		r2 = ranges[q][iq];
		if(intersect(r1, r2)){
			join(idxs[p][ip], idxs[q][iq]);
		}

		if(r1.second < r2.second){
			++ip;
		}else{
			++iq;
		}
	}
}

int main()
{
	scanf("%d", &N);
	for(int i=0;i<N;i++){
		scanf("%d%d", X+i, Y+i);
		Xs.push_back(X[i]);
		Xs.push_back(X[i]+1);
		Ys.push_back(Y[i]);
		Ys.push_back(Y[i]+1);
	}
	Xs.push_back(-2100000000);
	Xs.push_back(2100000000);
	Ys.push_back(-2100000000);
	Ys.push_back(2100000000);

	sort(Xs.begin(), Xs.end());
	sort(Ys.begin(), Ys.end());
	Xs.erase(unique(Xs.begin(), Xs.end()), Xs.end());
	Ys.erase(unique(Ys.begin(), Ys.end()), Ys.end());

	for(int i=0;i<N;i++){
		X[i] = lower_bound(Xs.begin(), Xs.end(), X[i]) - Xs.begin();
		//Y[i] = lower_bound(Ys.begin(), Ys.end(), Y[i]) - Ys.begin();
		Ycor[X[i]].push_back(Y[i]);
	}
	for(int i=0;i<Xs.size();i++){
		sort(Ycor[i].begin(), Ycor[i].end());

		int left = -2100000000;
		for(int j=0;j<Ycor[i].size();j++){
			int val = Ycor[i][j];
			if(left < val){
				ranges[i].push_back(make_pair(left, val)); //[left, val)
			}
			left = val + 1;
		}

		ranges[i].push_back(make_pair(left, 2100000000));
	}

	int bid = 0;
	for(int i=0;i<Xs.size();i++){
		for(int j=0;j<ranges[i].size();j++) idxs[i].push_back(bid++);
	}
	for(int i=0;i<bid;i++) uf[i] = -1;

	//join!!
	for(int i=1;i<Xs.size();i++){
		unify(i-1, i);
	}

	int ret = -1;
	for(int i=0;i<bid;i++) if(uf[i] < 0) ++ret;

	printf("%d\n", ret);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:56: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:58: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Judge Result