30 pts AC on #2,3,4 求调。
查看原帖
30 pts AC on #2,3,4 求调。
1296826
lcfollower楼主2024/6/8 14:36

rt。

#include<bits/stdc++.h>
#define int long long
#define _Dark_Star exit(0)
#define inf 0x3f3f3f3f
#define up(i,x,y) for(register int i=x;i<=y;i++)
#define dn(i,x,y) for(register int i=x;i>=y;i--)
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x*f;}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10|48);}
inline void writeln(int x){write(x),putchar('\n');}
inline void writesp(int x){write(x),putchar(' ');}
const int N = 1e5 + 10 , M = 2e6 + 10;
struct tree{
  int from , to;
  double w;
  inline bool operator <(const tree &b)const{
    if(w == b.w){
      if(from == b.from) return to < b.to;
      return from < b.from;
    }
    return w < b.w;
  }
}a[M];
int E,n,m;
int fa[N];
double ans;

inline int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
inline void merge(int x,int y){int fax = find(x) , fay = find(y);if(fax != fay) fa[fax] = fay;}
double b[N];
double c[N][2];

inline void kruskal(){
  for(int i = 1;i <= m;i ++){
    int u = find(a[i].from) ,v = find(a[i].to);
    if(u != v){
      merge(u,v);
      -- E;
      ans = a[i].w;
      if(!E) break;
    }
  } //writeln(ans);
} signed main(){
  srand(time(0));
  int num = read();
  up(i,1,num) fa[i] = i;
  E = num - 1;
  up(i,1,num) cin>>b[i];
  n = read();
  up(i,1,n) cin>>c[i][0]>>c[i][1];
  up(i,1,n) up(j,i+1,n) if(i != j){a[++m].from = i , a[m].to = j , a[m].w = sqrt(pow(c[i][1] - c[j][1],2) + pow(c[i][0] - c[j][0] , 2));}
  sort(a + 1 , a + 1 + m);
  kruskal();
  int tot = 0;
  up(i,1,num) if(b[i] >= ans) ++tot;
  writeln(tot);
  _Dark_Star;
}
2024/6/8 14:36
加载中...