快4s过的，但是排行榜上很多1s内，不知道如何优化。。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #define lson l, m, rt<<1 9 #define rson m+1, r, rt<<1|110 #define IO ios::sync_with_stdio(false);cin.tie(0);11 #define INF 0x3f3f3f3f12 typedef unsigned long long ll;13 using namespace std;14 int n, num, d, s, t, pre[10010];15 char c;16 typedef struct{17 int x, y;18 }Node;19 Node node[10010];20 int flag[10010];21 ll length(ll a, ll b)22 {23 return a*a+b*b;24 }25 int find(int x)26 {27 while(x != pre[x]){28 x = pre[x];29 }30 return x;31 }32 void join(int k)33 {34 int tx = find(k); 35 pre[k] = tx;//优化 36 for(int i = 1; i <= n; i++){37 if(flag[i]&&i != k){38 ll tmp = length(node[k].x-node[i].x, node[k].y-node[i].y);39 if(tmp<=d*d){ //一开始直接pre[i]=tx然后wa了，一定要是把根接上去 40 int ty = find(i);41 pre[i] = ty;//优化 42 if(tx != ty){43 pre[ty] = tx;44 }45 }46 }47 }48 }49 int main()50 {51 IO;52 memset(flag, 0, sizeof(flag));53 cin >> n >> d;54 for(int i = 1; i <= n; i++){55 pre[i] = i;56 }57 for(int i = 1; i <= n; i++){58 cin >> node[i].x >> node[i].y;59 } 60 while(cin >> c){61 if(c == 'O'){62 cin >> num;63 flag[num] = 1;64 join(num);65 }66 else if(c == 'S'){67 cin >> s >> t;68 int tx = find(s);69 pre[s] = tx; 70 int ty = find(t);71 pre[t] = ty;72 if(tx == ty) cout << "SUCCESS" << endl;73 else cout << "FAIL" << endl;74 }75 }76 return 0; 77 }