题目

分析

我们抽象的认为一些不能互相辨认的人，被分到了一个集合，每当又有一场演出，就将每个出演的演员扔出集合，再将上次在相同集合的分在同一集合。

然后修改被分的集合和被新创建的时间，当集合只有一个数的时候不可再分。

输出每个演员所在的集合的最后修改时间，仅当该演员所在的集合中只有一个演员。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const int mo=1000000007;

const int N=100005;

using namespace std;

int fa[N*20],tot,t[N*20],n,m,a[N],bz[N*20],d[N],num,sum[N];

int main()

{

	scanf("%d%d",&n,&m);

	sum[0]=n;

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

	{

		int k;

		scanf("%d",&k);

		num=0;

		for(int j=1;j<=k;j++)

		{

			scanf("%d",&a[j]);

			if(sum[fa[a[j]]]!=1 || bz[fa[a[j]]])

			{

				if(!bz[fa[a[j]]])

				{

					t[fa[a[j]]]=i;

					d[++num]=fa[a[j]];

						sum[fa[a[j]]]--;

					bz[fa[a[j]]]=++tot;

					fa[a[j]]=tot;

					t[tot]=i;

					sum[tot]=1;

				}

				else

				sum[fa[a[j]]]--,fa[a[j]]=bz[fa[a[j]]],sum[fa[a[j]]]++;

			}

		}

		for(int j=1;j<=num;j++)

			bz[d[j]]=0;

	}

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

		if(sum[fa[i]]==1)

			printf("%d ",t[fa[i]]);

		else printf("0 ");

}

巴特西

【JSOI2014】歌剧表演

题目

分析

最新文章

热门文章