QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491047 | #8759. 小班课 | DEMONKILLER | WA | 0ms | 4008kb | C++14 | 1.7kb | 2024-07-25 17:06:47 | 2024-07-25 17:06:47 |
Judging History
answer
#include<bits/stdc++.h>
#define N 510
using namespace std;
struct node{
int to,next;
}edge[N<<2];
vector<int> g[N<<1];
int T,n,m,ans,maxv,cnt,in[N],Ans[N],f[N],b[N],s[N],a[N][N],mat[N<<1],sum[N<<1],vis[N<<1],head[N];
void add(int from,int to){
edge[++cnt]={to,head[from]};
head[from]=cnt;
in[to]++;
}
void init(){
memset(in,0,sizeof(in));
memset(vis,0,sizeof(vis));
memset(mat,0,sizeof(mat));
memset(sum,0,sizeof(sum));
memset(head,0,sizeof(head));
memset(f,0,sizeof(f));
for(int i=1;i<=n+m;i++)g[i].clear();
ans=maxv=cnt=0;
}
bool dfs(int now,int tag){
if(vis[now]==tag)return false;
vis[now]=tag;
for(int v:g[now]){
if(sum[v]<b[v-n]){
mat[now]=v;
sum[v]++;
return true;
}
for(int j:g[v])
if(mat[j]==v&&dfs(j,tag)){
add(j,now);
mat[now]=v;
return true;
}
}
return false;
}
void Dfs(int now){
f[now]=1;
for(int i=head[now];i;i=edge[i].next)
if(!f[edge[i].to])Dfs(edge[i].to);
printf("%d ",now);
}
void solve(){
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=m;i++)scanf("%d",&b[i]);
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
maxv=max(maxv,s[i]);
for(int j=1;j<=s[i];j++){
scanf("%d",&a[i][j]);
g[i].emplace_back(a[i][j]+n);
g[a[i][j]+n].emplace_back(i);
}
}
for(int i=1;i<=n;i++)
if(dfs(i,i))ans++;
printf("%d\n",ans);
for(int i=1;i<=n;i++)
if(!in[i])Dfs(i);
putchar('\n');
}
int main(){
scanf("%d",&T);
while(T--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 4008kb
input:
3 5 5 1 1 1 1 1 4 1 3 2 4 1 5 4 3 4 2 1 2 3 5 1 1 5 3 1 2 2 2 1 2 2 1 2 2 1 3 2 1 3 2 1 3 5 5 1 1 1 1 1 2 1 2 2 5 4 2 3 2 2 4 3 2 5 1
output:
5 5 1 2 4 3 5 5 4 3 2 1 5 1 5 2 4 3
result:
wrong answer wrong rearrangement 4 5