QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#605112 | #8759. 小班课 | UESTC_DECAYALI | RE | 1ms | 4144kb | C++20 | 2.2kb | 2024-10-02 15:32:31 | 2024-10-02 15:32:31 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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 ...