QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491359#8759. 小班课maojunWA 5ms4960kbC++231.0kb2024-07-25 19:01:532024-07-25 19:01:54

Judging History

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

  • [2024-07-25 19:01:54]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:4960kb
  • [2024-07-25 19:01:53]
  • 提交

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]