1 solutions

  • 1
    @ 2026-10-10 21:57:32
    #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