QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113010#6550. Elimination RaceeyiigjknWA 1ms3416kbC++142.1kb2023-06-15 20:49:262023-06-15 20:49:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-15 20:49:29]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3416kb
  • [2023-06-15 20:49:26]
  • 提交

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