QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#354731 | #6555. Sets May Be Good | yyyyxh | WA | 1ms | 3860kb | C++14 | 1.4kb | 2024-03-15 22:02:41 | 2024-03-15 22:02:41 |
Judging History
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'