Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

把=写成==

Posted by Qiandl at 2017-06-27 19:18:55
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

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

struct UnionFind {
	int root[1001];
	UnionFind(int n) {
		for (int i = 0; i < n; i++) {
			root[i] = i;
		}
	}

	int getroot(int n) {
		if (n == root[n])return n;
		return root[n] = getroot(root[n]);
	}

	bool is_same(int a, int b) {
		return getroot(a) == getroot(b);
	}

	void unite(int a, int b) {
		a = getroot(a), b = getroot(b);
		if (a != b) {
			root[a] = b;
		}
	}
};

int N, d;
P p[1001];
bool is_act[1001];

int POW_TWO(int a) {
	return a * a;
}

bool can_connecting(int a, int b) {
	return POW_TWO(p[a].first - p[b].first) + POW_TWO(p[a].second - p[b].second) <= d * d;
}

int main() {
	cin >> N >> d;
	for (int i = 0; i < N; i++) {
		cin >> p[i].first >> p[i].second;
	}
	UnionFind uf(N); 
	for (int i = 0; i < N; i++)is_act[i] = false;
	char c;
	while (cin >> c) {
		if (c == 'O') {
			int a;
			cin >> a, a--;
			is_act[a] = true;
			for (int i = 0; i < N; i++) {
				if (can_connecting(a, i) && is_act[i])uf.unite(a, i);
			}
		}
		else {
			int a, b;
			cin >> a >> b, a--, b--;
			if (uf.is_same(a, b))cout << "SUCCESS" << endl;
			else cout << "FAIL" << endl;
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator