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 SmilingWang at 2009-05-11 21:23:28 on Problem 2236
#include <iostream>
using namespace std;


const int DefaultSize = 10;

class UFSets{
public:	
	UFSets(int sz = DefaultSize);
	virtual ~UFSets(){delete[] parent;};
	UFSets & operator = (UFSets & R);
	void Union(int Root1, int Root2);
	int Find(int x);
	
	void weightedUnion(int Root1, int Root2);
	int CollapsingFind(int i);
private:
	int * parent;
	int size;
};

UFSets::UFSets(int sz){
	int i;
	this->size = sz;
	parent  = new int[size];
	for(i = 0; i < sz; i++){
		parent[i] = -1;
	}
}

UFSets& UFSets::operator =(UFSets & R){
	if(this == &R){
		return *this;
	}
	int i;
	delete[] parent;
	parent = new int[R.size];
	for(i = 0 ; i < R.size; i++){
		parent[i] = R.parent[i];
	}
	return *this;
}

void UFSets::Union(int Root1, int Root2){
	if(Root1 == Root2){
		return;
	}
	parent[Root1] += parent[Root2];
	parent[Root2] = Root1;
}

int UFSets::Find(int x){
	while(parent[x] >= 0){
		x = parent[x];
	}
	return x;
}

void UFSets::weightedUnion(int Root1, int Root2){
	int r1 = Find(Root1);
	int r2 = Find(Root2);
	if(r1 != r2){
		int temp = parent[r1] + parent[r2];
		if(r1 > r2){
			parent[r2] = temp;
			parent[r1] = r2;
		}
		else{
			parent[r1] = temp;
			parent[r2] = r1;
		}
	}
}

int UFSets::CollapsingFind(int i){
	int j;
	for(j = i; parent[j] >= 0; j = parent[j]);

	while(i != j){
		int temp = parent[i];
		parent[i] = j;
		i = temp;
	}

	return i;
}

struct Point{
	int id;
	int x;
	int y;
	bool ok;
};

int main(){
	int n, d;

	Point arr[1010];

	cin >> n;
	cin >> d;
	

	for(int i = 0; i < n; i++){
		int x;
		int y;
		cin >> x;
		cin >> y;
		arr[i].x = x;
		arr[i].y = y;
		arr[i].id = i;
		arr[i].ok = false;
	}
	UFSets* ufs = new UFSets(n);

	char op;

	while(cin>> op){

		if(op == 'O'){
			int id;
			cin >> id;
			id--;
			arr[id].ok = true;
			for(int j = 0; j < n; j++){
				if(id == j){
					continue;
				}
				if(arr[j].ok){
					if(((arr[j].x-arr[id].x)*(arr[j].x - arr[id].x) + (arr[j].y - arr[id].y)*(arr[j].y - arr[id].y)) <= d*d){
						int fj = ufs->Find(j);
						int fid = ufs->Find(id);
						if(fj != fid){   //去掉判断就WA
							ufs->Union(id, j);
						}
					}
				}
			}
		}
		else if(op == 'S'){
			int x, y;
			cin >> x;
			cin >> y;
			x--;
			y--;
			if(x == y){
				cout << "SUCCESS"<<endl;
			}
			else if(ufs->Find(x) == ufs->Find(y)){
				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