QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#113010 | #6550. Elimination Race | eyiigjkn | WA | 1ms | 3416kb | C++14 | 2.1kb | 2023-06-15 20:49:26 | 2023-06-15 20:49:29 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
constexpr int INF=1e9;
int n,a[510][510],b[510][510],mch[1010],dep[1010],lst[510];
bitset<510> nvis,E[510],D[510];
bool bfs()
{
int l=1,r=1,mxd=INF;
static int que[1010];
nvis.set();
for(int i=1;i<n;i++)
if(!mch[i+n]) dep[que[r++]=i+n]=1;
while(l<r)
{
int u=que[l++];
if(dep[u]>=mxd) continue;
if(u<=n)
{
if(!mch[u]) mxd=dep[u];
else if(!dep[mch[u]]) dep[que[r++]=mch[u]]=dep[u];
}
auto tmp=E[u-n]&nvis;
for(int v=tmp._Find_first();v<=n;v=tmp._Find_next(v))
dep[que[r++]=v]=dep[u]+1,nvis.reset(v);
}
return mxd<INF;
}
bool dfs(int u)
{
auto tmp=E[u-n]&D[dep[u]+1]&nvis;
for(int v=tmp._Find_first();v<=n;v=tmp._Find_next(v))
if(nvis.test(v) && (!mch[v] || (nvis.reset(v),dfs(mch[v]))))
return mch[u]=v,mch[v]=u,true;
return false;
}
void slv(int x)
{
int cnt=0;
for(int i=1;i<n;i++)
{
E[i].reset();
for(int j=b[i][x]+1;j<=n;j++) E[i].set(a[i][j]);
}
while(bfs())
{
nvis.set();
for(int i=1;i<=n;i++) D[dep[i]].set(i);
for(int i=1;i<n;i++)
if(!mch[i+n]) cnt+=dfs(i+n);
for(int i=1;i<=n;i++) D[dep[i]].reset(i);
}
if(cnt<n-1) return cout<<"No\n",void();
cout<<"Yes\n";
static bool v1[510],v2[510];
for(int i=1;i<n;i++) lst[i]=a[i][n];
for(int i=1;i<n;i++)
{
int p=0;
for(int j=1;j<n && !p;j++)
if(mch[j+n]==lst[j]) p=j;
if(p)
{
cout<<p<<" \n"[i==n-1];
v1[p]=v2[lst[p]]=1;
for(int j=1;j<n;j++)
{
int k=b[j][lst[j]];
while(v2[a[j][k]]) k--;
lst[j]=a[j][k];
}
}
else
{
int p=1,u1,u2;
static int nxt[510];
for(int i=1;i<n;i++)
if(!v1[i]) nxt[i]=mch[lst[i]]-n;
for(p=1;v1[p];p++);
u1=u2=p;
do u1=nxt[u1],u2=nxt[nxt[u2]];while(u1!=u2);
while(1)
{
mch[u1+n]=lst[u1];mch[lst[u1]]=u1+n;
if((u1=nxt[u1])==u2) break;
}
i--;
}
}
fill(mch+1,mch+2*n,0);
fill(v1+1,v1+n,0);
fill(v2+1,v2+n+1,0);
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n;
for(int i=1;i<n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j],b[i][a[i][j]]=j;
for(int i=1;i<=n;i++) slv(i);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3416kb
input:
4 1 2 3 4 2 1 3 4 4 3 1 2
output:
Yes 2 1 3 No No No
result:
ok n=4, yes=1, no=3
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3404kb
input:
3 2 1 3 2 1 3
output:
No No No
result:
wrong answer Jury has the answer but participant has not