| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为何总是超时?#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator