QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#490115#8759. 小班课rizynvuWA 1ms3980kbC++141.4kb2024-07-25 11:23:282024-07-25 11:23:28

Judging History

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

  • [2024-07-25 11:23:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3980kb
  • [2024-07-25 11:23:28]
  • 提交

answer

#include<bits/stdc++.h>
const int maxn = 5e2 + 10;
std::vector<int> A[maxn], B[maxn];
int mat[maxn], vis[maxn], siz[maxn];
int n, m;
inline int dfs(int u) {
   for (int v : A[u]) {
      if (vis[v]++)
         continue;
      for (int &w : B[v])
         if (! w || dfs(w))
            return w = u, mat[u] = v, 1;
   }
   return 0;
}
inline void Main() {
   scanf("%d%d", &n, &m);
   for (int i = 1, k; i <= m; i++)
      scanf("%d", &k), B[i].clear(), B[i].resize(k);
   for (int i = 1, k; i <= n; i++) {
      scanf("%d", &k), A[i].resize(k);
      for (int &x : A[i]) scanf("%d", &x);
   }
   int ans = 0;
   for (int i = 1; i <= n; i++) {
      memset(vis, 0, sizeof(int) * (m + 1));
      mat[i] = 0, ans += dfs(i);
   }
   printf("%d\n", ans);
   memset(siz, 0, sizeof(int) * (m + 1));
   for (int i = 1; i <= n; i++)
      siz[mat[i]]++;
   memset(vis, 0, sizeof(int) * (n + 1));   
   for (int f = 1; f--; ) {
      for (int i = 1; i <= n; i++)
         if (! vis[i]) {
            int fl = 1;
            for (int j : A[i]) {
               if (j == mat[i]) break;
               fl &= ! siz[j];
            }
            if (fl) {
               printf("%d ", i);
               f = 1, vis[i] = 1, siz[mat[i]]--;
               break;
            }
         }
   }
   puts("");
}
int main() {
   int T; scanf("%d", &T);
   while (T--) Main();
   return 0;
}

詳細信息

Test #1:

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

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: 0
Accepted
time: 0ms
memory: 3908kb

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
1 
2
1 2 
2
1 2 
1
1 
0
1 
0
1 
1
1 2 
0
1 
2
1 2 
1
1 
0
1 
1
1 2 
0
1 
0
1 
0
1 
2
1 2 
2
2 1 
1
1 
1
1 2 
1
1 2 
1
1 
1
1 2 
1
1 
1
1 2 
0
1 2 
1
1 
1
1 
0
1 
1
1 
2
1 2 
0
1 
0
1 
1
1 2 
2
1 2 
0
1 
0
1 
0
1 
0
1 2 
2
1 2 
1
1 
1
1 
0
1 
0
1 
0
1 
1
1 
1
1 
0
1 
2
1 2 
2
1 2 
1
1 2 
1
1...

result:

ok Correct!

Test #3:

score: 0
Accepted
time: 1ms
memory: 3892kb

input:

166
3 3
1 1 1
0
2 2 3
0
3 3
0 3 0
0
2 1 3
0
3 3
0 0 3
0
2 2 3
0
3 3
2 0 1
2 2 3
0
2 3 2
3 3
0 2 1
2 3 1
0
2 2 1
3 3
1 1 1
2 3 1
2 1 2
1 3
3 3
2 1 0
1 3
0
0
3 3
1 1 1
1 2
0
2 2 3
3 3
1 1 1
0
1 2
2 2 1
3 3
0 0 3
1 1
2 1 3
1 3
3 3
0 1 2
2 2 3
2 2 3
0
3 3
2 0 1
0
1 1
0
3 3
1 2 0
2 2 1
1 1
0
3 3
1 0 2
0
...

output:

1
1 2 3 
0
1 2 3 
1
1 2 3 
1
1 2 3 
2
1 2 3 
3
3 1 2 
0
1 2 3 
2
1 2 3 
2
1 2 3 
2
1 2 3 
2
2 1 3 
1
1 2 3 
2
1 2 3 
1
1 2 3 
1
1 2 3 
2
1 2 3 
2
1 2 3 
0
1 2 3 
2
1 2 3 
0
1 2 3 
1
1 2 3 
2
1 2 3 
1
1 2 3 
3
1 2 3 
3
1 2 3 
0
1 2 3 
1
1 2 3 
2
1 2 3 
2
1 2 3 
2
2 1 3 
2
1 2 3 
1
1 2 3 
2
1 2 3 
1
1...

result:

ok Correct!

Test #4:

score: 0
Accepted
time: 1ms
memory: 3980kb

input:

125
4 4
3 1 0 0
1 2
0
2 1 3
3 2 3 1
4 4
2 0 1 1
2 1 3
2 1 2
2 4 1
0
4 4
2 0 1 1
2 2 3
3 3 2 4
1 2
0
4 4
0 1 1 2
2 3 1
1 4
3 1 2 4
0
4 4
1 1 1 1
2 3 2
2 4 2
0
2 4 2
4 4
2 2 0 0
3 2 1 4
2 3 4
1 2
1 3
4 4
2 0 0 2
1 2
3 3 2 1
2 3 2
2 2 1
4 4
1 2 0 1
1 4
0
0
0
4 4
3 0 0 1
3 2 1 3
0
2 1 4
2 4 3
4 4
1 2 1 ...

output:

3
1 2 3 4 
3
2 1 3 4 
2
1 2 3 4 
3
1 2 3 4 
3
1 3 4 2 
2
2 3 1 4 
2
1 2 3 4 
1
1 2 3 4 
3
1 2 3 4 
3
2 3 1 4 
0
1 2 3 4 
2
1 2 3 4 
2
1 2 3 4 
2
1 2 3 4 
4
2 3 4 1 
2
1 2 3 4 
2
1 2 3 4 
2
1 2 3 4 
3
2 3 1 4 
4
1 2 3 4 
3
1 2 3 4 
1
1 2 3 4 
2
1 3 2 4 
3
1 2 3 4 
2
1 2 3 4 
4
1 2 3 4 
2
1 2 3 4 
3
1...

result:

ok Correct!

Test #5:

score: 0
Accepted
time: 1ms
memory: 3896kb

input:

100
5 5
2 1 2 0 0
0
2 3 2
3 5 4 3
2 1 2
0
5 5
0 2 0 0 3
1 5
0
1 1
0
0
5 5
0 1 3 0 1
2 5 4
2 1 5
0
0
3 3 1 4
5 5
1 1 0 2 1
1 2
0
2 4 5
0
1 4
5 5
0 1 1 2 1
2 4 2
0
2 1 3
0
1 1
5 5
0 0 2 2 1
2 4 3
1 4
0
3 5 4 1
3 5 1 2
5 5
1 2 1 0 1
2 1 2
0
3 3 5 2
2 4 3
0
5 5
1 0 1 1 2
0
1 4
1 3
1 3
0
5 5
1 2 1 1 0
1 ...

output:

3
1 3 2 4 5 
1
1 2 3 4 5 
2
1 2 3 4 5 
3
1 2 4 5 3 
2
1 2 3 4 5 
4
2 3 5 4 1 
3
1 2 4 3 5 
2
1 2 3 4 5 
1
1 2 3 4 5 
4
1 2 3 4 5 
2
1 2 3 4 5 
2
1 2 3 4 5 
3
1 2 3 4 5 
3
2 3 4 1 5 
3
1 2 3 4 5 
3
1 3 2 4 5 
2
1 2 3 4 5 
3
1 2 3 4 5 
1
1 2 3 4 5 
3
1 2 3 4 5 
1
1 2 3 4 5 
2
1 2 3 4 5 
2
1 2 3 4 5 
2...

result:

ok Correct!

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 3900kb

input:

10
45 47
3 0 2 0 1 1 1 0 2 0 1 0 0 3 0 0 0 4 0 1 0 0 1 2 1 1 1 0 1 1 1 0 0 0 0 1 0 0 0 1 2 4 1 2 1 2 3
7 1 37 21 3 13 43 22
0
10 23 46 22 40 12 19 47 27 16 42
4 29 19 45 35
10 6 26 2 43 41 7 9 16 42 44
5 39 40 34 46 14
3 34 3 38
8 10 5 38 23 19 37 9 34
0
5 31 29 15 13 35
3 40 4 28
1 7
6 29 12 9 35 2...

output:

33
1 2 7 9 11 12 14 16 17 19 20 21 22 23 25 26 27 28 29 5 31 32 33 36 37 10 4 18 24 35 38 39 8 3 6 34 40 15 41 44 30 13 42 43 45 
39
1 3 4 8 10 12 13 14 15 16 18 20 22 24 27 30 33 35 36 37 38 11 39 6 23 25 28 31 40 9 21 5 34 41 42 43 7 19 44 2 45 17 26 29 32 
36
1 4 7 8 9 12 13 14 17 20 21 18 23 2 2...

result:

wrong answer Integer 47 violates the range [1, 45]