90分RE求调
  • 板块灌水区
  • 楼主gw2381
  • 当前回复7
  • 已保存回复7
  • 发布时间2024/8/19 21:22
  • 上次更新2024/8/20 08:42:29
查看原帖
90分RE求调
1279550
gw2381楼主2024/8/19 21:22

第九个样例过不了,WA了好久了,QwQ,大佬麻烦看一看

#include<bits/stdc++.h>
using namespace std;
long long n,m,fa[200010],x[200010],y[200010],k,h[200010],ans,ra[200010];
bool kil[200010],vis[200010];
long long find_father(long long num)
{
	if(fa[num]==num)
	{
		return num;
	}
	return fa[num]=find_father(fa[num]);
}
vector <long long> line[200010],point[200010];
int main()
{
	scanf("%lld%lld",&n,&m);
	for(long long i=0;i<n;i++)
	{
		fa[i]=i;
	}
	for(long long i=1;i<=m;i++)
	{
		scanf("%lld%lld",&x[i],&y[i]);
		line[x[i]].push_back(i);
		line[y[i]].push_back(i);
		point[x[i]].push_back(y[i]);
		point[y[i]].push_back(x[i]);
	}
	scanf("%lld",&k);
	for(long long i=1;i<=k;i++)
	{
		scanf("%lld",&h[i]);
		kil[h[i]]=true;
	}
	ans=n-k;
	for(long long i=0;i<n;i++)
	{
		if(kil[i]==false)
		{
			for(long long j=0;j<line[i].size();j++)
			{
				if(vis[line[i][j]]==false)
				{
					if(kil[point[i][j]]==false)
					{
						long long xf=find_father(i),yf=find_father(point[i][j]);
						vis[line[i][j]]=true;
						if(xf!=yf)
	                    {
	                    	ans--;
		                    fa[xf]=yf;
	                    }
					}
				}
			}
		}
	}
	ra[k]=ans;
	for(long long i=k;i>=1;i--)
	{
		kil[h[i]]=false;
		long long lg=0;
		for(long long j=0;j<line[h[i]].size();j++)
		{
			if(vis[line[h[i]][j]]==false)
			{
				if(kil[point[h[i]][j]]==false)
				{
					long long xf=find_father(h[i]),yf=find_father(point[h[i]][j]);
					vis[line[h[i]][j]]=true;
					if(xf!=yf)
	                {
	                   	lg++;
		                fa[xf]=yf;
	                }
				}
			}
		}
		ans-=lg-1;
		ra[i-1]=ans;
	}
	for(long long i=0;i<=k;i++)
	{
		printf("%lld\n",ra[i]);
	}
} 

这是记录:

https://www.luogu.com.cn/record/173676189

orz orz

2024/8/19 21:22
加载中...