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

暴力才1329ms!还是用的STL,看来此题数据很弱。

Posted by KatrineYang at 2016-07-19 16:43:32 on Problem 2236
#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:
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