QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#490128#8759. 小班课rizynvuRE 1ms3896kbC++141.5kb2024-07-25 11:34:002024-07-25 11:34:01

Judging History

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

  • [2024-07-25 11:34:01]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3896kb
  • [2024-07-25 11:34:00]
  • 提交

answer

#include<bits/stdc++.h>
const int maxn = 5e2 + 10;
int n, m;
std::vector<int> A[maxn], B[maxn];
int mat[maxn], vis[maxn], siz[maxn];
inline int dfs(int u) {
   for (int v : A[u]) {
      if (v == mat[u] || 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] = std::vector<int>(k, 0);
   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);
   }
   for (int i = 1; i <= n; i++)
      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 T = n; T--; ) {
      bool f = 0;
      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;
            }
         }
      assert(f);
   }
   puts("");
}
int main() {
   int T; scanf("%d", &T);
   while (T--) Main();
   return 0;
}

详细

Test #1:

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

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: 3784kb

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: 3784kb

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
1 2 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: -100
Runtime Error

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:


result: