QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491359 | #8759. 小班课 | maojun | WA | 5ms | 4960kb | C++23 | 1.0kb | 2024-07-25 19:01:53 | 2024-07-25 19:01:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,b[N],k[N],a[N][N],p[N][N];
#define mem(a) memset(a,0,sizeof a)
bool vs[N];int to[N];
bool dfs(int u){
if(vs[u])return 0;vs[u]=1;
for(int i=1;i<=k[u];i++){
int v=a[u][i];
for(int j=1;j<=b[v];j++)
if(!p[v][j]||dfs(p[v][j])){p[v][j]=u;to[u]=i;return 1;}
}
return 0;
}
inline void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d",&b[i]);
for(int i=1;i<=n;i++){scanf("%d",&k[i]);for(int j=1;j<=k[i];j++)scanf("%d",&a[i][j]);}
int cnt=0;mem(to);mem(p);
for(int i=1;i<=n;i++){mem(vs);cnt+=dfs(i);}
mem(vs);static int c[N];mem(c);
for(int i=1;i<=n;i++){
// printf("to=%d\n",a[i][to[i]]);
c[a[i][to[i]]]++;
}
printf("%d\n",cnt);
for(int t=1;t<=n;t++)for(int i=1;i<=n;i++)if(to[i]&&!vs[i]){
bool fl=1;
for(int j=1;j<to[i];j++)if(c[a[i][j]]){fl=0;break;}
if(fl){printf("%d ",i);vs[i]=1;c[a[i][to[i]]]--;}
}
puts("");
}
int main(){
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4812kb
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 2 4 5 1 3 5 5 1 2 3 4 5 1 5 2 4 3
result:
ok Correct!
Test #2:
score: -100
Wrong Answer
time: 5ms
memory: 4960kb
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 1 2 0 2 1 2 2 1 2 1 1 0 0 1 1 0 2 1 2 1 1 0 1 1 0 0 0 2 1 2 2 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 0 1 1 1 1 0 1 1 2 1 2 0 0 1 1 2 1 2 0 0 0 0 2 1 2 1 1 1 1 0 0 0 1 1 1 1 0 2 1 2 2 1 2 1 2 1 1 0 0 2 1 2 1 1 1 1 0 0 1 1 2 1 2 0 2 2 1 0 2 1 ...
result:
wrong answer Integer 2 violates the range [1, 1]