| Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
|---|---|---|---|---|---|---|---|---|---|
| 38988 | swzzzz | 【S】T4 | C++ | 通过 | 100 | 241 MS | 1708 KB | 2602 | 2025-11-26 21:35:33 |
#include<bits/stdc++.h> using namespace std; #define N 1145 int n,m,p[N]; bitset<N>a[N]; int faCnt[N]; bool in[N][N]; bool vis[N]; void solve(){ cin>>n>>m; memset(vis,0,sizeof(vis)); memset(in,0,sizeof(in)); memset(faCnt,0,sizeof(faCnt)); for(int i=1;i<=n;i++) a[i].reset(); for(int i=1,j;i<=m;i++){ cin>>p[i]; for(int k=1;k<=p[i];k++){ cin>>j; if(p[i]>1) a[j][i]=1; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j) continue; if((a[i]|a[j])==a[j]){ // cout<<i<<' '<<j<<' '<<a[i].to_string()<<' '<<a[j].to_string()<<endl; in[i][j]=1; faCnt[i]++; } } } // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++){ // cout<<in[i][j]<<' ';} // cout<<endl; // } // for(int i=1;i<=m;i++) cout<<p[i]<<' '; // cout<<endl; for(int stp=1;stp<n;stp++){ // cout<<"--------------"<<endl; // for(int i=1;i<=n;i++){ // for(int j=1;j<=m;j++){ // if(a[i][j]) cout<<j<<' '; // } // cout<<endl; // } int son=0,fa; for(int i=1;i<=n;i++){ if(vis[i] || !faCnt[i]) continue; for(int j=1;j<=n;j++){ if(i==j || vis[j]) continue; if(in[i][j]){ son=i,fa=j; break; } } if(son) break; } if(!son){ cout<<"NO"<<endl; return; } // cout<<son<<' '<<fa<<endl; vis[son]=1; for(int i=1;i<=n;i++){ if(i==fa || vis[i]) continue; if(in[i][son]){ in[i][son]=0; faCnt[i]--; } } for(int i=1;i<=m;i++){ if(a[son][i]){ a[son][i]=0; p[i]--; if(p[i]==1){ a[fa][i]=0; p[i]=0; } } } // for(int i=1;i<=m;i++) cout<<p[i]<<' '; // cout<<endl; for(int i=1;i<=n;i++){ if(i==fa || vis[i]) continue; if((a[fa]|a[i])==a[i]){ in[fa][i]=1; faCnt[fa]++; } } } cout<<"YES"<<endl; } int main(){ ios::sync_with_stdio(0); int t; cin>>t; while(t--) solve(); return 0; }