QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#605112#8759. 小班课UESTC_DECAYALIRE 1ms4144kbC++202.2kb2024-10-02 15:32:312024-10-02 15:32:31

Judging History

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

  • [2024-10-02 15:32:31]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:4144kb
  • [2024-10-02 15:32:31]
  • 提交

answer

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cassert>
#define RI register int
#define CI const int&
using namespace std;
const int N=505,INF=1e9;
int T,n,m,b[N],valid[N],mat[N],val[N*N],pre[N*N],rb[N],L[N],R[N],vis[N*N]; vector <int> v[N],a[N];
inline bool find(CI now,CI idx)
{
    for (auto to:v[now]) if (vis[to]!=idx)
    {
        vis[to]=idx;
        if (!pre[to]||find(pre[to],idx))
        return pre[to]=now,1;
    }
    return 0;
}
int main()
{
   	//freopen("1.in","r",stdin);
    for (scanf("%d",&T);T;--T)
    {
        scanf("%d%d",&n,&m);
        for (RI i=1;i<=n;++i) valid[i]=1,v[i].clear(),mat[i]=0;
        int idx=0;
        for (RI i=1;i<=m;++i)
        {
            scanf("%d",&b[i]);
            L[i]=idx+1;
            for (RI j=1;j<=b[i];++j) val[++idx]=i;
            R[i]=idx;
        }
        for (RI i=1;i<=n;++i)
        {
            int x; scanf("%d",&x); a[i].resize(x);
            for (RI j=0;j<a[i].size();++j)
            {
                scanf("%d",&a[i][j]);
                for (RI k=L[a[i][j]];k<=R[a[i][j]];++k)
                v[i].push_back(k);
            }
        }
        for (RI i=1;i<=idx;++i) pre[i]=vis[i]=0;
        int flow=0;
        for (RI i=1;i<=n;++i) flow+=find(i,i);
        printf("%d\n",flow);
        for (RI i=1;i<=idx;++i)
        if (pre[i]) ++rb[mat[pre[i]]=val[i]];
        //for (RI i=1;i<=n;++i) printf("%d%c",mat[i]," \n"[i==n]);
        vector <int> ans;
        for (RI k=1;k<=n;++k)
        {
            bool find=0;
            for (RI i=1;i<=n;++i)
            {
                if (!mat[i]||!valid[i]) continue;
                bool flag=1;
                for (auto x:a[i])
                {
                    if (x==mat[i]) break;
                    if (rb[x]>0) { flag=0; break; }                                                     
                }
                if (flag)
                {
                    ans.push_back(i); valid[i]=0;
                    --rb[mat[i]]; find=1; break;
                }
            }
            assert(find==1);
        }
        for (auto x:ans) printf("%d ",x); putchar('\n');
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4144kb

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
Runtime Error

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:


result: