QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#490105#8759. 小班课rizynvuWA 1ms3972kbC++141.5kb2024-07-25 11:21:132024-07-25 11:21:13

Judging History

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

  • [2024-07-25 11:21:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3972kb
  • [2024-07-25 11:21:13]
  • 提交

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] && mat[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;
            }
         }
   }
   for (int i = 1; i <= n; i++)
      if (! vis[i])
         printf("%d ", i);
   puts("");
}
int main() {
   int T; scanf("%d", &T);
   while (T--) Main();
   return 0;
}

詳細信息

Test #1:

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

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: 1ms
memory: 3972kb

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

result:

ok Correct!

Test #3:

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

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

result:

ok Correct!

Test #4:

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

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

result:

ok Correct!

Test #5:

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

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

result:

ok Correct!

Test #6:

score: -100
Wrong Answer
time: 0ms
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 7 11 12 14 16 17 19 21 25 29 5 31 36 37 10 4 18 24 35 38 39 8 3 6 34 40 15 44 30 13 42 43 2 9 20 22 23 26 27 28 32 33 41 45 
39
1 3 10 12 14 15 16 18 20 24 30 33 35 36 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 4 8 13 22 27 37 
36
1 4 8 17 20 21 18 23 2 25 27 5 29 6 1...

result:

wrong answer wrong rearrangement 37 39