QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#441601#8759. 小班课ship2077WA 1ms3924kbC++142.2kb2024-06-14 16:34:192024-06-14 16:34:19

Judging History

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

  • [2024-06-14 16:34:19]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3924kb
  • [2024-06-14 16:34:19]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int M=505;
int n,m,k,x,N,ans;
int b[M],match1[M];
bool vis[M],tmp[M];
vector<int>vec[M],match2[M];
int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
    return x;
}
bool match(int x){
    for (auto y:vec[x]){
        if (vis[y]) continue;vis[y]=1;
        if (match2[y].size()<b[y]){
            match2[y].emplace_back(x);   
            match1[x]=y;return 1;
        }
        for (auto &nxt:match2[y])
            if (match(nxt)) return match1[x]=y,nxt=x,1;
    } return 0;
}
void solve(){
    n=read();m=read();N=ans=0;
    for (int i=1;i<=m;i++){
        int x=read();vis[i]=0;
        if (x) b[++N]=x,vis[i]=1;
    }
    for (int i=1;i<=n;i++){
        k=read();vec[i].clear();
        while (k--) if (vis[x=read()])
            vec[i].emplace_back(x);
        reverse(vec[i].begin(),vec[i].end());
    }
    for (int i=1;i<=n;i++) match1[i]=0;
    for (int i=1;i<=m;i++) match2[i].clear();
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) vis[j]=0;
        if (match(i)) ans++;
    }
    for (int i=1;i<=n;i++){ vis[i]=0;
        while (!vec[i].empty()&&match2[vec[i].back()].empty())
            vec[i].pop_back();
    }
    printf("%d\n",ans);
    while (ans){
        for (int i=1;i<=n;i++) tmp[i]=vis[i];
        for (int i=1;i<=n;i++)
            if (match1[i]&&!vis[i]){
                int x=i; while (!tmp[x])
                    tmp[x]=1,x=match2[vec[x].back()].back();
                int j=x; while (1){
                    printf("%d ",j);vis[j]=1;ans--;
                    int tmp=vec[j].back();
                    j=match2[tmp].back();
                    match2[tmp].pop_back();
                    if (j==x) break;
                }
                for (int i=1;i<=n;i++)
                    while (!vec[i].empty()&&match2[vec[i].back()].empty())
                        vec[i].pop_back();
                break;
            }
    }
    for (int i=1;i<=n;i++)
        if (!match1[i]) printf("%d ",i);
    puts("");
}
int main(){int T=read();while (T--) solve();return 0;}

詳細信息

Test #1:

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

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 4 1 3 2 
5
3 2 1 4 5 
5
2 5 1 3 4 

result:

ok Correct!

Test #2:

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

input:

250
2 1
2
1 1
1 1
1 1
1
0
2 2
1 1
1 1
2 2 1
2 2
0 2
2 1 2
1 2
1 1
1
1 1
1 2
1 0
0
1 2
1 0
0
2 1
2
1 1
0
1 2
1 0
0
2 1
2
1 1
1 1
1 1
1
1 1
1 2
1 0
1 2
2 2
2 0
1 1
1 2
1 1
1
0
1 1
1
0
1 2
0 1
1 1
2 2
1 1
1 1
2 1 2
2 2
1 1
2 2 1
2 2 1
1 2
0 1
1 2
2 1
2
1 1
0
2 2
2 0
1 1
1 2
1 1
1
1 1
2 1
2
0
1 1
1 1
1
...

output:

2
2 1 
0
1 
2
1 2 
1
1 2 
1
1 
0
1 
0
1 
1
1 2 
0
1 
2
2 1 
1
1 
0
1 
1
1 2 
0
1 
0
1 
0
1 
2
1 2 
2
1 2 
1
1 
1
1 2 
1
1 2 
1
1 
1
2 1 
1
1 
1
2 1 
0
1 2 
1
1 
1
1 
0
1 
1
1 
2
1 2 
0
1 
0
1 
1
1 2 
2
2 1 
0
1 
0
1 
0
1 
0
1 2 
1
1 2 
1
1 
1
1 
0
1 
0
1 
0
1 
1
1 
1
1 
0
1 
2
2 1 
2
2 1 
1
2 1 
1
1...

result:

wrong answer wrong answer