POJ 2443Set Operation(美题! 每32位压缩处理)

POJ 2443Set Operation(好题! 每32位压缩处理)
Set OperationTime Limit: 3000MS Memory Limit: 65536KTotal Submissions: 2286 Accepted: 876

Description

You are given N sets, the i-th set (represent by S(i)) have C(i) element (Here "set" isn't entirely the same as the "set" defined in mathematics, and a set may contain two same element). Every element in a set is represented by a positive number from 1 to 10000. Now there are some queries need to answer. A query is to determine whether two given elements i and j belong to at least one set at the same time. In another word, you should determine if there exist a number k (1 <= k <= N) such that element i belongs to S(k) and element j also belong to S(k).

Input

First line of input contains an integer N (1 <= N <= 1000), which represents the amount of sets. Then follow N lines. Each starts with a number C(i) (1 <= C(i) <= 10000), and then C(i) numbers, which are separated with a space, follow to give the element in the set (these C(i) numbers needn't be different from each other). The N + 2 line contains a number Q (1 <= Q <= 200000), representing the number of queries. Then follow Q lines. Each contains a pair of number i and j (1 <= i, j <= 10000, and i may equal to j), which describe the elements need to be answer.

Output

For each query, in a single line, if there exist such a number k, print "Yes"; otherwise print "No".

Sample Input

33 1 2 33 1 2 51 1041 31 53 51 10

Sample Output

YesYesNoNo

Hint

The input may be large, and the I/O functions (cin/cout) of C++ language may be a little too slow for this problem.

题目大意：题目意思很简单，给你n个集合，每个集合有若干个元素。问你是否存在一个集合使得a,b都在里面。
 解题思路：现在考虑时间复杂度，n为10^3,元素的个数为10^4,查询语句q为10^5.自己开始写的是直接10^5*10^3，还需要考虑测试数据的组数，这样查找肯定会超时。当时用vector，把一个元素出现的行保存起来，查找的时候看元素a在哪些行出现过，然后枚举这些行是否出现过b。那样访问的次数就会少很多，不过还是很险会超时，2800ms.
 题目地址：Set Operation
没有压缩处理的AC代码：

#include<iostream>#include<cstring>#include<string>#include<cmath>#include<cstdio>#include<set>#include<vector>using namespace std;int n;short visi[1002][10002];int p[10002][32]; //把每个元素存在每32行压缩到到一个int内int main(){    int i,j,k,t,x,q,flag;    int a,b;    int len;  //分成32位的长度    while(~scanf("%d",&n))    {        for(i=0;i<n;i++)            for(j=1;j<=10000;j++)                visi[i][j]=0;        for(i=1;i<=n;i++)        {            scanf("%d",&t);            for(j=0;j<t;j++)            {                scanf("%d",&x);                visi[i][x]=1;            }        }        len=n/32;        if(n%32!=0)            len++;        for(i=0;i<len-1;i++)   //压缩处理        {            for(j=1;j<=10000;j++)            {                p[j][i]=0;                int tmp=1;                for(k=1+i*32;k<=32+i*32;k++)                {                    p[j][i]+=visi[k][j]*tmp;                    tmp<<=1;                }            }        }        for(j=1;j<=10000;j++)        {            p[j][i]=0;            int tmp=1;            for(k=1+i*32;k<=n;k++)            {                p[j][i]+=visi[k][j]*tmp;                tmp<<=1;            }        }        scanf("%d",&q);        for(i=0;i<q;i++)        {            flag=0;            scanf("%d%d",&a,&b);            for(j=0;j<len;j++)            {                if(p[a][j]&p[b][j])  //两个相与得到1说明有一行a,b都存在                {                    flag=1;                    break;                }            }            if(flag) printf("Yes\n");            else printf("No\n");        }    }    return 0;}//891MS

查看更多 下一篇