| ||||||||||
| 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 | |||||||||
暴力才1329ms!还是用的STL,看来此题数据很弱。#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
bool yibu[1010][1010] = {false};
vector<int> reps[1010];
int main() {
int N, d;
scanf("%d%d", &N, &d);
int X[1010], Y[1010];
bool good[1010] = {false};
int rep[1010] = {0};
for(int i = 1; i <= N; i++){
int x, y;
scanf("%d%d", &x, &y);
X[i] = x, Y[i] = y;
}
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(i == j) continue;
if((X[i]-X[j])*(X[i]-X[j]) + (Y[i]-Y[j])*(Y[i]-Y[j]) <= d*d){
yibu[i][j] = true;
yibu[j][i] = true;
}
}
}
char c;
while(scanf("%c", &c) > 0){
if(c == 'O'){
int ss;
scanf("%d", &ss);
good[ss] = true;
int argmax, maxsize = 0;
vector<int> temp;
for(int i = 1; i <= N; i++){
if(yibu[i][ss] && good[i]){
temp.push_back(i);
int size = reps[rep[i]].size();
if(size > maxsize){
maxsize = size;
argmax = rep[i];
}
}
}
if(temp.size() == 0){
rep[ss] = ss;
reps[ss].push_back(ss);
}
else{
rep[ss] = argmax;
reps[argmax].push_back(ss);
int sz = temp.size();
for(int i = 0; i < sz; i++){
if(rep[temp[i]] == argmax) continue;
int thisRep = rep[temp[i]];
int thisSize = reps[thisRep].size();
for(int j = 0; j < thisSize; j++){
rep[reps[thisRep][j]] = argmax;
reps[argmax].push_back(reps[thisRep][j]);
}
}
}
}
if(c == 'S'){
int s1, s2;
scanf("%d%d", &s1, &s2);
if(good[s1] && good[s2] && rep[s1] == rep[s2]){
printf("SUCCESS\n");
}
else{
printf("FAIL\n");
}
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator