1 solutions
-
1
#include<iostream> #include<cstdio> #include<queue> #include<cmath> using namespace std; struct nod { int x,y; }; struct edg { int u,v,w; bool operator <(const edg &B) const { return w>B.w; } }; const int NR=1001,MR=501; int p[NR],f[NR]; nod a[NR]; int fnd(int x) { if(f[x]==x) return x; return f[x]=fnd(f[x]); } int main() { int m,n,i,j,T,ans=0; cin>>m; for(i=1;i<=m;i++) cin>>p[i]; cin>>n; for(i=1;i<=n;i++) { f[i]=i; cin>>a[i].x>>a[i].y; } priority_queue<edg> pq; for(i=1;i<n;i++) for(j=i+1;j<=n;j++) pq.push({i,j,sqrt((a[j].x-a[i].x)*(a[j].x-a[i].x)+(a[j].y-a[i].y)*(a[j].y-a[i].y))}); i=0; while(i<n-1 && !pq.empty()) { int x=pq.top().u,y=pq.top().v,t=pq.top().w; pq.pop(); if(fnd(x)!=fnd(y)) { T=t; i++; f[fnd(x)]=f[y]; } } for(i=1;i<=m;i++) if(p[i]>=T) ans++; cout<<ans; return 0; }
- 1
Information
- ID
- 1522
- Time
- 1000ms
- Memory
- 125MiB
- Difficulty
- 5
- Tags
- # Submissions
- 3
- Accepted
- 3
- Uploaded By