题意

B 君的第三题(urumqi)

题目描述

风雨如晦，鸡鸣不已。

B 君最近在研究自己的学长都在做什么工作，每个学长属于一个公司。

B 君会获得一些信息，比如x 和y 在相同公司，x 和y 在不同公司。

如果当前信息和之前记住的所有信息都不矛盾，B 君会记住这条信息，否则B 君会指出矛盾。

你需要输出B 君是记住了信息，还是指出了矛盾。

输入格式

第一行一个整数n。

接下来n 行，每行三个整数x; y; p。

如果p = 1，这条信息表示x 和y 在相同公司。

如果p = 0，这条信息表示x 和y 在不同公司。

输出格式

对于每条信息，输出一个字符串Yes 或No。

如果这条信息和之前记住的所有信息不矛盾，输出Yes，并且记住这条信息。

如果这条信息和之前记住的所有信息矛盾，输出No，并且不记住这条信息。

样例输入

3

1 2 1

1 3 1

2 3 0

样例输出

Yes

Yes

No

数据规模与约定

对于100% 的数据，满足\(1 \leq n \leq 100000, 1 \leq x, y \leq 10^8, 0 \leq p \leq 1\)。

对于50% 的数据，满足\(n \leq 1000\)。

对于50% 的数据，满足\(x, y \leq 100\)。

以上两部分数据有25% 的交集。

分析

维护在同一个公司可以用并查集，关键在于如何维护不在同一公司中。

维护不在同一公司中可以用set，合并的时候更新就行了。

set可以启发式合并，但是不启发式也行。

B君：这题不好出数据卡不启发式合并，所以std也就没写启发式合并

代码

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<algorithm>

#include<complex>

#define rg register

#define il inline

#define co const

#pragma GCC optimize ("O0")

using namespace std;

template<class T> il T read()

{

    T data=0;

	int w=1;

    char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return data*w;

}

template<class T> il T read(T&x)

{

	return x=read<T>();

}

typedef long long ll;

const int INF=0x7fffffff;

const int MAXN=2e5+7;

int v[MAXN],len;

int x[MAXN],y[MAXN],p[MAXN];

int fa[MAXN];

int find(int x)

{

	return fa[x]==x?x:fa[x]=find(fa[x]);

}

set<int>S[MAXN];

int main()

{

  freopen("urumqi.in","r",stdin);

  freopen("urumqi.out","w",stdout);

	int n=read<int>();

	for(int i=1;i<=n;++i)

	{

		read(x[i]);read(y[i]);read(p[i]);

		v[++len]=x[i],v[++len]=y[i];

	}

	sort(v+1,v+len+1);

	len=unique(v+1,v+len+1)-v-1;

	for(int i=1;i<=n;++i)

	{

		x[i]=lower_bound(v+1,v+len+1,x[i])-v;

		y[i]=lower_bound(v+1,v+len+1,y[i])-v;

	}

	for(int i=1;i<=len;++i)

	{

		fa[i]=i;

	}

	for(int i=1;i<=n;++i)

	{

		int x=::x[i],y=::y[i];

		x=find(x),y=find(y);

		if(p[i]==1)

		{

			if(S[x].find(y)!=S[x].end())

			{

				puts("No");

			}

			else

			{

				puts("Yes");

				if(x==y)

					continue;

				fa[x]=y;

				for(auto i:S[x])

				{

					int z=i;

					S[z].erase(x);

					S[z].insert(y);

				}

				S[y].insert(S[x].begin(),S[x].end());

				S[x].clear();

			}

		}

		else

		{

			if(x==y)

			{

				puts("No");

			}

			else

			{

				puts("Yes");

				S[x].insert(y);

				S[y].insert(x);

			}

		}

	}

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}