QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#441601 | #8759. 小班课 | ship2077 | WA | 1ms | 3924kb | C++14 | 2.2kb | 2024-06-14 16:34:19 | 2024-06-14 16:34:19 |
Judging History
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;}
Details
Tip: Click on the bar to expand more detailed information
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