Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
38980 baka24 【S】T4 C++ 通过 100 80 MS 404 KB 1981 2025-11-26 19:16:30

Tests(11/11):


#include<bits/stdc++.h> using namespace std; #define int long long #define inx(u) int I=h[(u)],v=edge[I].v,w=edge[I].w;I;I=edge[I].nx,v=edge[I].v,w=edge[I].w #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back bool AAA; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} const int MAXN=1010,N=10,inf=1e18,Mod=1e9+7; int n,m,p[MAXN],s[MAXN][MAXN],d[MAXN],inq[MAXN]; bitset<MAXN>a[MAXN]; queue<pii>Q; int chk(int x){ for(int i=1;i<=n;i++)if(!d[i]&&i!=x&&((a[i]&a[x])==a[x]))return i; return 0; } bool ers(int x,int y){ d[x]=1; bool res=0; for(int i=1;i<=m;i++)if(a[x][i]){ p[i]--; if(p[i]==1){ a[y][i]=0; res|=1; } a[x][i]=0; } return res; } void slv(){ n=read(),m=read(); for(int i=1;i<=n;i++)a[i].reset(),inq[i]=d[i]=0; for(int i=1;i<=m;i++){ p[i]=read(); if(p[i]==1)p[i]=read(),i--,m--; else for(int j=0;j<p[i];j++)a[read()][i]=1; } // for(int i=1;i<=n;i++,cout<<endl)for(int j=1;j<=m;j++)cout<<a[i][j]; for(int i=1;i<=n;i++){ int j=chk(i); // cout<<i<<" "<<j<<endl; if(j&&ers(i,j)&&!inq[j]){ int tmp=chk(j); if(tmp)Q.push(mk(j,tmp)),inq[j]=1; } } while(!Q.empty()){ int i=Q.front().fr,j=Q.front().sc;Q.pop(); if(ers(i,j)&&!inq[j]){ int tmp=chk(j); if(tmp)Q.push(mk(j,tmp)),inq[j]=1; } } int cnt=0; for(int i=1;i<=n;i++)cnt+=!d[i]; puts(cnt<=1?"YES":"NO"); } bool BBB; signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); int _=read();while(_--) slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; cerr<<((&AAA)-(&BBB))/1024.0/1024<<"mb\n"; return 0; }


测评信息: