CF1468M Similar Sets 题解
考虑根号分治。设 \(m=\sum k_i\)，则把 \(k>\sqrt m\) 的称为大集合，\(k\leq \sqrt m\) 的称为小集合。
对于小集合与小集合：
暴力枚举每个集合的每一对 \((x,y)\)，开一个哈希表维护有没有其他的集合也存在这个数对。由于集合大小不超过 \(\sqrt m\)，复杂度可以证明最大是 \(O(m\sqrt m)\)。
对于大集合和其他集合：
枚举大集合的所有数放到哈希表里，暴力扫其他每个集合，判断是否相似。由于大集合的个数最多 \(O(\sqrt m)\)，所以这部分复杂度是 \(O(m\sqrt m)\) 的，然后就做完了。
点击查看代码
#pragma GCC optimize(2)
#include
#include
#include
#include
#include
#include
#include
#define mp std::make_pair
#define fi first
#define se second
typedef std::pair pii;
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int K=150;
const int N=2e5+13;
int n,m,len[N],small[N],big[N],c[N],from[N];
std::vector a[N];
int ms[1][N];
std::vector vis[N];
/*struct HashTable//map int to T
{
#define T int//int can be replaced by the class you want
#define T_0 0//0 can be replaced by the zero item of T
inline void swap(int *&x,int *&y){ int *t=x;x=y;y=t; }
inline void swap(bool *&x,bool *&y){ bool *t=x;x=y;y=t; }
inline unsigned long long xor64(){ static unsigned long long x=19260817; return x^=x<<13,x^=x>>17,x^=x<<7; }
inline bool is_prime(int x){ if(x==1) return 0; for(int i=2;i*i<=x;i++) if(x%i==0) return 0; return 1; }
inline int abs(int x){ return x<0?-x:x; }
//inline void swap(T *&x,T *&y){ T *t=x;x=y;y=t; }//if T is not int, this should be used
int *a;bool *used;
T *b;
int m,c1,c2,c3,c4;
int size;
inline HashTable(){ a=NULL,b=NULL,used=NULL; }
inline void clear(){ if(a) delete[] a,delete[] b,delete[] used,a=NULL,b=NULL,used=NULL; size=0; }
inline int hash(const int &x,const int &t){ return ((long long)c1*x+c2+t*(((long long)c3*x%m+c4)%(m-1)+1))%m; }
inline int _insert(int x,T y){ int p=hash(x,0),t=0; while(used[p]&&a[p]!=x) p=hash(x,++t); if(a[p]==x) return -p; used[p]=1,a[p]=x,b[p]=y; return p; }
inline void resize(int n){ int last=m;m=n+!(n&1); while(!is_prime(m)) m+=2; int *ta=new int[m];T *tb=new T[m];bool *tused=new bool[m]; memset(tused,0,sizeof(bool)*m);swap(ta,a),swap(tb,b),swap(tused,used); c1=xor64()%(m-1)+1,c2=xor64()%(m-1)+1,c3=xor64()%(m-1)+1,c4=xor64()%(m-1)+1; for(int i=0;im) resize((size*2+1)*2+1); int p=hash(x,0),t=0; while(used[p]&&a[p]!=x) p=hash(x,++t); if(a[p]==x) return -p; used[p]=1,a[p]=x,b[p]=y,size++; return p; }
inline int find(int x){ int p=hash(x,0),t=0; while(used[p]&&a[p]!=x) p=hash(x,++t); if(a[p]==x) return p; return -1; }
inline int erase(int p){ return find(p)==-1?-1:used[find(p)]=0; }
inline int& operator [] (int x){ return b[abs(insert(x,T_0))]; }
#undef T
#undef T_0
}ms[N];*/
int main(){
int T=rd();while(T--){
n=rd();m=0;int cntt=0;
for(int i=1;i<=n;++i) a[i].clear();
for(int i=1;i<=n;++i){
len[i]=rd();m+=len[i];
for(int j=1;j<=len[i];++j){
int x=rd();
a[i].push_back(x);
c[++cntt]=x;
}
}
std::sort(c+1,c+cntt+1);cntt=std::unique(c+1,c+cntt+1)-(c+1);
for(int i=1;i<=n;++i)
for(int j=0;jy) std::swap(x,y);
vis[x].push_back(mp(y,p));
}
}
}
for(int i=1;i<=cntt;++i){
for(auto x:vis[i]){
if(from[x.fi]){game_over=1;ansx=from[x.fi],ansy=x.se;break;}
from[x.fi]=x.se;
}
for(auto x:vis[i]) from[x.fi]=0;
if(game_over) break;
}
if(game_over){printf("%d %d\n",ansx,ansy);continue;}
for(int i=1;i<=lb;++i){
int p=big[i];
for(int j=1;j<=cntt;++j) ms[0][j]=0;
for(int j=0;j=2){game_over=1;ansx=p,ansy=q;break;}
}
if(game_over) break;
}
if(game_over) break;
for(int j=1;j<=ls;++j){
int q=small[j],cnt=0;
for(int k=0;k=2){game_over=1;ansx=p,ansy=q;break;}
}
if(game_over) break;
}
if(game_over) break;
}
if(game_over){printf("%d %d\n",ansx,ansy);continue;}
puts("-1");
}
return 0;
}
//M