QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354731#6555. Sets May Be GoodyyyyxhWA 1ms3860kbC++141.4kb2024-03-15 22:02:412024-03-15 22:02:41

Judging History

你现在查看的是最新测评结果

  • [2024-03-15 22:02:41]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3860kb
  • [2024-03-15 22:02:41]
  • 提交

answer

#include <cstdio>
#include <bitset>
#define for_bset(i,j) \
	for(int j=f[i]._Find_first();j!=N;j=f[i]._Find_next(j))
using namespace std;
int n,m;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=1000,P=998244353;
bitset<N> f[N],del;
int res,pw[N+1];
inline void inc(int &x,int v){(x+=v)>=P&&(x-=P);}
int main(){
	n=read();m=read();
	for(int i=0;i<m;++i){
		int u=read()-1,v=read()-1;
		f[u].set(v);f[v].set(u);
	}
	pw[0]=1;
	for(int i=1;i<=n;++i) (pw[i]=(pw[i-1]<<1))>=P&&(pw[i]-=P);
	bool par=0;int cc=0,cur=n;
	for(int i=0;i<n;++i){
		if(del[i]) continue;
		del.set(i);--cur;
		int sz=0,pos=-1;
		bool tag=0,rev=f[i][i];
		f[i].reset(i);
		for_bset(i,j){
			f[j].reset(i);f[i].reset(j);
			if(sz){
				if(tag) f[j].flip(j);
				f[j]^=f[pos];
			}
			else{
				tag=f[j][j];f[j].reset(j);pos=j;
				del.set(j);--cur;
				if(rev){
					if(tag) par^=1;
					for_bset(j,k) f[k].reset(j),f[k].flip(k),f[k]^=f[i];
				}
				else for_bset(j,k) f[k].reset(j),f[k]^=f[i];
				f[j].reset();
			}
			++sz;
		}
		if(sz){
			inc(res,pw[cur+cc]);
			++cc;
		}
		else{
			if(rev){
				inc(res,pw[cur+cc]);
				printf("%d\n",res);
				return 0;
			}
			++cc;
		}
	}
	if(!par) inc(res,pw[cc]);
	printf("%d\n",res);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3756kb

input:

5 5
1 2
2 3
3 4
4 5
1 5

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

3 0

output:

8

result:

ok 1 number(s): "8"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

2 1
1 2

output:

3

result:

ok 1 number(s): "3"

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3860kb

input:

4 6
1 2
1 3
1 4
2 3
2 4
3 4

output:

8

result:

wrong answer 1st numbers differ - expected: '6', found: '8'