QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#606142 | #8759. 小班课 | reaepita | WA | 0ms | 3976kb | C++14 | 1.8kb | 2024-10-02 22:25:08 | 2024-10-02 22:25:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e2 + 5;
int t[maxn];
int a[maxn][maxn], s[maxn];
int to[maxn], cnt[maxn];
int num[maxn][maxn], vis[maxn];
int ans = 0;
bool dfs(int now, int tag)
{
if (vis[now] == tag)
return false;
vis[now] = tag;
for (int i = 1; i <= s[now]; i++)
{
int v = a[now][i];
for (int j = 1; j <= t[v]; j++)
if (!num[v][j] || dfs(num[v][j], tag))
{
to[now] = v;
num[v][j] = now;
return true;
}
}
return false;
}
int n, m;
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
memset(vis, 0, sizeof(vis));
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d", &t[i]);
for (int i = 1; i <= n; i++)
{
scanf("%d", &s[i]);
for (int j = 1; j <= s[i]; j++)
scanf("%d", &a[i][j]);
}
for (int i = 1; i <= n; i++)
if (dfs(i, i))
ans++;
printf("%d\n", ans);
for (int i = 1; i <= n; i++)
cnt[to[i]]++;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (vis[j])
continue;
bool flag = true;
for (int k = 1; a[j][k] != to[j]; k++)
if (cnt[a[j][k]])
{
flag = false;
break;
}
if (flag)
{
vis[j] = 1;
printf("%d ", j);
cnt[to[j]]--;
break;
}
}
printf("\n");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3976kb
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 7 7
result:
wrong answer Integer 7 violates the range [1, 5]