QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#625330 | #9449. New School Term | as_lyr | WA | 0ms | 9820kb | C++14 | 2.3kb | 2024-10-09 18:42:07 | 2024-10-09 18:42:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=11000,M=1100000;
int n,m;
int u[M],v[M];
pair <int,bool> f[N];
vector <int> e[N][2];
inline pair <int,bool> find(int x){
if(f[x].first==x)
return f[x];
pair <int,bool> pr=find(f[x].first);
return f[x]=make_pair(pr.first,pr.second^f[x].second);
}
bitset <N> bs[N];
inline bool check(int x,int y,bool op){
int sum=0;
vector <int> p;
for(int i=1;i<=n;i++){
if(f[i].first!=i)
continue;
if(i==x)
continue;
int siz[2]={(int)e[i][0].size(),(int)e[i][1].size()};
if(i==y){
siz[0]+=e[i][op^1].size();
siz[1]+=e[i][op].size();
}
sum+=min(siz[0],siz[1]);
p.push_back(siz[0]+siz[1]-min(siz[0],siz[1]));
}
int tot=0;
bs[0]=0;
bs[0][sum]=1;
sort(p.begin(),p.end());
for(int l=0,r=0;l<(int)p.size();l=r+1){
r=l;
while(r<(int)p.size()-1&&p[r+1]==p[l])
r++;
int val=p[l],cnt=r-l+1;
for(int k=0;cnt>(1<<k);k++){
cnt-=1<<k;
tot++;
bs[tot]=bs[tot-1]|(bs[tot-1]<<(val*(1<<k)));
}
tot++;
bs[tot]=bs[tot-1]|(bs[tot-1]<<(val*cnt));
}
return op^bs[tot][n/2];
}
inline void merge(int x,int y){
pair <int,int> prx=find(x),pry=find(y);
x=prx.first,y=pry.first;
if(x==y)
return ;
if(e[x][0].size()+e[x][1].size()>e[y][0].size()+e[y][1].size())
swap(x,y);
bool op=check(x,y,prx.second^pry.second);
f[x]=make_pair(y,op);
for(int o=0;o<2;o++)
for(int a:e[x][o])
e[y][o^op].push_back(a);
}
bool ans[N];
int dp[N][N];
int main(){
scanf("%d%d",&n,&m);
n*=2;
for(int i=m;i;i--)
scanf("%d%d",&u[i],&v[i]);
for(int i=1;i<=n;i++){
f[i]=make_pair(i,0);
e[i][0].push_back(i);
}
for(int i=1;i<=m;i++)
merge(u[i],v[i]);
int tot=0;
dp[0][0]=1;
for(int i=1;i<=n;i++)
if(f[i].first==i){
tot++;
int siz[2]={(int)e[i][0].size(),(int)e[i][1].size()};
for(int j=siz[0];j<=n/2;j++)
dp[tot][j]|=dp[tot-1][j-siz[0]];
for(int j=siz[1];j<=n/2;j++)
dp[tot][j]|=dp[tot-1][j-siz[1]];
}
for(int i=n,x=n/2;i;i--)
if(f[i].first==i){
int siz[2]={(int)e[i][0].size(),(int)e[i][1].size()};
bool op=1;
if(x>=siz[0]&&dp[tot-1][x-siz[0]]){
op=0;
x-=siz[0];
}
else
x-=siz[1];
for(int a:e[i][op])
ans[a]=1;
tot--;
}
for(int i=1;i<=n;i++)
putchar(ans[i]+'0');
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9820kb
input:
2 4 1 3 2 4 1 4 1 2
output:
1000
result:
wrong answer The number of 0s must be equal to that of 1s.