CF1949F 题解

CF1949F

思路

不合法情况要么完全包含要么不交。按 \(k_i\) 大小从小到大排序。实时记录每个爱好 \(j\) 对应的最后的人 \(f_j\)。当枚举到 \(i\) 时，枚举 \(i\) 的每个爱好 \(j\)，如果最后不合法意味着每个 \(f_j\) 的爱好都被 \(i\) 完全包含，枚举 \(f_j\) 所有爱好判断，否则找到一组解。如果最后不合法，所有 \(f_j\) 的爱好数之和为 \(k_i\)，所以复杂度瓶颈在排序的 \(O(n\log n)\)。

code

int n,m;
vector<int> a[maxn];
int id[maxn],f[maxn];
bool cmp(int u,int v){return a[u].size()<a[v].size();}
bool vis[maxn];
void work(){n=read();m=read();for(int i=1;i<=n;i++){int x=read();while(x--){int u=read();a[i].push_back(u);}id[i]=i;}sort(id+1,id+n+1,cmp);for(int i=1;i<=n;i++){for(int j:a[id[i]])vis[j]=1;for(int j:a[id[i]])if(f[j]!=id[i]){if(!f[j])f[j]=id[i];else{int p=f[j];for(int k:a[p]){if(!vis[k]){printf("YES\n%lld %lld\n",p,id[i]);return ;}f[k]=id[i];}}}for(int j:a[id[i]])vis[j]=0;}printf("NO\n");
}