QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#491047#8759. 小班课DEMONKILLERWA 0ms4008kbC++141.7kb2024-07-25 17:06:472024-07-25 17:06:47

Judging History

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

  • [2024-07-25 17:06:47]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4008kb
  • [2024-07-25 17:06:47]
  • 提交

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();
}

详细

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