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