zoj 3509

zoj 3509题目大意:N个点,M次加边/删边/询问两点连通性操作,初始图为空。N题解:想什么呢,大力bitset!N*N*M/32花式水过!附代码:#include#defineN510usingnamespacestd;bitsets[N],ned,now,emp;intn,m;inlineboolquery(inta,intb){ ned=now=s[a

大家好,又见面了,我是你们的朋友全栈君。

题目大意:

N个点,M次加边/删边/询问两点连通性操作,初始图为空。N<=500,M<=50000,每条边最多加一次。

题解:

想什么呢,大力bitset!N*N*M/32花式水过!

附代码:

#include<bits/stdc++.h>
#define N 510
using namespace std;
bitset<N> s[N],ned,now,emp;
int n,m;
inline bool query(int a,int b){
	ned=now=s[a];ned[a]=0;
	int ta;
	while((ta=ned._Find_first())!=N){
		ned[ta]=0;
		ned|=(now|s[ta])^now;
		now|=s[ta];
		if(now[b]) return 1;
	}
	return now[b];
}
int main(){
	char ch[5];int a,b;
	int tot=0;
	while(~scanf("%d%d",&n,&m)){
		if(tot) puts("");
		for(int i=0;i<n;i++){
			s[i]=emp;
			s[i][i]=1;
		}
		printf("Case %d:\n",++tot);
		while(m--){
			scanf("%s%d%d",ch,&a,&b);
			a--,b--;
			if(ch[0]=='I') s[a][b]=s[b][a]=1;
			else if(ch[0]=='D') s[a][b]=s[b][a]=0;
			else{
				if(a==b) puts("YES");
				else if(query(a,b)) puts("YES");
				else puts("NO");
			}
		}
	}
	return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/158017.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • pytorch中的loss函数_pytorch loss不下降

    pytorch中的loss函数_pytorch loss不下降1)两个分布很接近,但是与0和1不接近,loss仍然很大,只适合分类2)mse只计算两个差异,做回归用的,数据相同,bceloss比mseloss大。3)SmoothL1Loss比mseloss小4)bceloss收敛比较快5)bcelossinput必须是0-1之间,targets可以不是6)target是0.5input是0.4与0.6,loss无正…

  • PD快速充电协议(转)[通俗易懂]

    PD快速充电协议(转)[通俗易懂]来源-作者@:http://www.elecfans.com/d/647097.html建议读者阅读原文,确保获得完整的信息1.PD充电协议是什么意思    PD充电协议是USB-IF组织公布的功率传输协议,它可以使目前默认最大功率5V/2A的type-c接口提高到100W,同时谷歌宣布Android7.0以上的手机搭载的快充协议必须支持PD协议,意在统一快充市场。2.PD协议快充是什么意思   …

    2022年10月23日
  • 0基础如何自学软件编程开发

    0基础如何自学软件编程开发0基础如何自学软件编程开发?学习软件编程首先需要选择一门编程语言,如C或JAVA语言,作为基础编程语言学习,掌握语言的逻辑,学习语法,其实编程实质上就是思路的运用,编程思路有了再想学习其他的编程语言就会变得顺风顺水。软件编程开发,对于现在的学生来讲到底有多重要呢?现在是互联网快速发展的时期,在几年前谁都没有想到人们在手机上就可以完成衣食住行等所有的活动,互联网也在慢慢的改变着未来一代人。互联网广泛覆盖了我们的生活,真正实现了“远在天边,近在眼前”,在我们的生活工作中都有互联网存在的身影,随着IT行业的越

  • spring中过滤器和拦截器_springboot拦截器顺序

    spring中过滤器和拦截器_springboot拦截器顺序拦截器与过滤器的区别:1、过滤器和拦截器触发时机不一样,过滤器是在请求进入容器后,但请求进入servlet之前进行预处理的。请求结束返回也是,是在servlet处理完后,返回给前端之前。如下图:2、拦截器可以获取IOC容器中的各个bean,而过滤器就不行,因为拦截器是spring提供并管理的,spring的功能可以被拦截器使用,在拦截器里注入一个service,可以调用业务逻辑…

  • 2020美赛C题解题思路(A Wealth of Data)[通俗易懂]

    2020美赛C题解题思路(A Wealth of Data)[通俗易懂](占个坑,B题已写完并发布,现正写C题)《数学建模想获奖?国赛、美赛看这一个就够了》——数学建模的进阶指南!内容全面、门类齐全,包含组队、日常训练、算法(含MATLAB代码)、建模、写作和“高校内部培训资源”等诸多方面的指导!千载难逢、不容错过!——有条件的朋友们支持一下,谢谢!需要“数学建模国赛美赛资源包”的关注公众号“猫和真人”,回复“1”即可获得资源包,有条件的支持一下哈!…

  • vue前后台数据交互vue-resource文档

    vue前后台数据交互vue-resource文档

    2021年10月11日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号