QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#428458#8759. 小班课Glacia_OfficialWA 19ms5840kbC++141.4kb2024-06-01 19:39:112024-06-01 19:39:12

Judging History

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

  • [2024-06-01 19:39:12]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:5840kb
  • [2024-06-01 19:39:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

int t, n, m, k, x, a[505], match[505][505], tog[505], vis[505];
vector<int> G[505];
int dfs(int x) {
	if (exchange(vis[x], 1)) {
		return 0;
	}
	for (auto y : G[x]) {
		for (int i = 0; i < a[y]; i++) {
			if (!match[y][i] || dfs(match[y][i])) {
				match[y][i] = x;
				return 1;
			}
		}
	}
	return 0;
}
signed main() {
	scanf("%lld", &t);
	while (t--) {
		memset(tog, 0, sizeof(tog));
		memset(match, 0, sizeof(match));
		scanf("%lld%lld", &n, &m);
		for (int i = 1; i <= m; i++) {
			scanf("%lld", &a[i]);
		}
		for (int i = 1; i <= n; i++) {
			G[i].clear();
			scanf("%lld", &k);
			while (k--) {
				scanf("%lld", &x);
				G[i].push_back(x);
			}
		}
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			memset(vis, 0, sizeof(vis));
			ans += dfs(i);
		}
		printf("%lld\n", ans);
		for (int i = 1; i <= m; i++) {
			for (int j = 0; j < a[i]; j++) {
				if (match[i][j]) {
					tog[match[i][j]] = i;
				}
			}
		}
		memset(vis, 0, sizeof(vis));
		while (true) {
			for (int i = 1; i <= n; i++) {
				if (vis[i] || !tog[i]) {
					continue;
				}
				for (auto x : G[i]) {
					if (a[x] && x != tog[i]) {
						break;
					} else if (a[x]) {
						printf("%lld ", i);
						vis[i] = 1;
						a[tog[i]]--;
						goto aaa;
					}
				}
			}
			break;
			aaa:;
		}
		puts("");
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5840kb

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

result:

ok Correct!

Test #2:

score: -100
Wrong Answer
time: 19ms
memory: 5784kb

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]