bzoj 4195程序自动分析
2024-09-07 02:30:28
先离散一下,然后并查集就好了。
(一开始作大死,没全离散,WA一片)
#include<bits/stdc++.h>
#define INF 0x7fffffff
#define LL long long
#define N 1000005
using namespace std;
inline int ra()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
int fa[N],b[N],n,m,cnt,tot,sum;
bool flag;
struct node{
int x,y;
}ask[N],a[N];
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
int T=ra();
while (T--)
{
map<int ,int > mp; sum=;
n=ra(); cnt=; tot=; flag=;
for (int i=; i<=n; i++)
{
int x=ra(),y=ra(),z=ra();
if (z==)
{
b[++sum]=x; b[++sum]=y;
ask[++cnt].x=x,ask[cnt].y=y;
}
else {
a[++tot].x=x; a[tot].y=y;
b[++sum]=x; b[++sum]=y;
}
}
sort(b+,b+sum+);
int len=unique(b+,b+sum+)-b;
unique(b+,b+sum+);
for (int i=; i<len; i++)
mp[b[i]]=i;
for (int i=; i<=sum; i++) fa[i]=i;
for (int i=; i<=tot; i++)
{
int q=find(mp[a[i].x]),p=find(mp[a[i].y]);
if (q!=p)
fa[p]=q;
}
for (int i=; i<=cnt; i++)
{
int q=find(mp[ask[i].x]),p=find(mp[ask[i].y]);
if (p==q)
{
cout<<"NO"<<endl;
flag=;
break;
}
}
if (!flag) cout<<"YES"<<endl;
}
return ;
}
最新文章
- ks
- 创建一个点状注记(MarkerElement)
- queen8
- linux 内核邮件列表
- 随笔:近期仍在流行的QQ盗号网页简析
- thinkphp自动验证中的静态验证和动态验证和批量验证
- Nginx 服务器性能参数设置
- C语言中的const
- Xcode 7在支持ipad的设备中需要支持分屏!
- python学习笔记27(python中sys模块的使用)
- new[] class deconstructor
- /etc/group文件详解
- SqlServer发送邮件,定时作业
- SuperWebClient -一个基于CURL的.NET HTTP/HTTPS模拟神组件(2)
- 原生javascript选项卡
- 使用Update Strategy组件无法进行delete操作
- vimrc配置
- 【Python3练习题 002】企业发放的奖金根据利润提成
- tomcat 服务器故障排除
- Event Tracing For Windows