QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#217397#6550. Elimination Race275307894aWA 0ms4104kbC++142.3kb2023-10-16 20:32:422023-10-16 20:32:44

Judging History

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

  • [2023-10-16 20:32:44]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4104kb
  • [2023-10-16 20:32:42]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__uint128_t;
const int N=5e2+5,M=N*8+5,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-6;const int INF=1e9+7;mt19937 rnd(263082);
int n,m,A[N][N],mch[N],pre[N];
bitset<N> B[N],vis;
int dfs(int x){
	while(1){
		int p=(B[x]&vis)._Find_first();
		if(p>n) break;
		vis[p]=0;
		if(!mch[p]||dfs(mch[p])) return mch[p]=x,pre[x]=p,1;
	}
	return 0;
}
int Get(){
	fill(mch+1,mch+n+1,0);
	for(int i=1;i<n;i++){
		vis.set();if(!dfs(i)) return 0;
	}
	return 1;
}
int scc[N];
namespace Tarjan{
	int dfn[N],low[N],st[N],sh,vis[N],Ct,dh;
	void Cl(){for(int i=1;i<=n;i++) dfn[i]=low[i]=vis[i]=st[i]=0;sh=Ct=0;}
	void tarjan(int x){
		dfn[x]=low[x]=++dh;st[++sh]=x;vis[x]=1;
		for(int i=1;i<=n;i++) if(B[x][i]){
			if(!dfn[i]) tarjan(i),low[x]=min(low[x],low[i]);
			else if(vis[i]) low[x]=min(low[x],dfn[i]);
		}
		if(low[x]>=dfn[x]) {++Ct;while(st[sh+1]^x) scc[st[sh]]=Ct,vis[st[sh--]]=0;}
	}
	void BD(){for(int i=1;i<n;i++) if(!dfn[i]) tarjan(i);}
}
int R[N],op[N],del[N];
void construct(){
	int Ct=0,i,j;
	for(i=1;i<=n;i++) R[i]=n,op[i]=del[i]=0;
	for(j=1;j<n;j++){
		for(i=1;i<n;i++) if(!del[i]) while(op[A[i][R[i]]]) R[i]--;
		for(i=1;i<n;i++) if(!del[i]&&scc[pre[i]]==scc[A[i][R[i]]]) {op[A[i][R[i]]]=1;del[i]=1;printf("%d ",i);break;}
		// cerr<<R[n-1]<<'\n';
	}
	printf("\n");
}
void Solve(){
	int i,j,h;scanf("%d",&n);
	for(i=1;i<n;i++) for(j=1;j<=n;j++) scanf("%d",&A[i][j]);
	for(i=1;i<=n;i++){
		for(j=1;j<n;j++) B[j].reset();
		for(j=1;j<n;j++) for(h=n;h;h--) if(A[j][h]^i) B[j][A[j][h]]=1;else break;
		if(!Get()) {puts("No");continue;}
		puts("Yes");
		for(j=1;j<=n;j++) B[j].reset();
		for(j=1;j<n;j++) for(h=n;h>1;h--) if(A[j][h]^pre[j]) B[A[j][h-1]][A[j][h]]=1;else break;
		Tarjan::Cl();Tarjan::BD();
		construct();
	}
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 0ms
memory: 3988kb

input:

3
2 1 3
2 1 3

output:

No
Yes
1 2 
No

result:

ok n=3, yes=1, no=2

Test #3:

score: 0
Accepted
time: 0ms
memory: 4072kb

input:

2
1 2

output:

Yes
1 
No

result:

ok n=2, yes=1, no=1

Test #4:

score: 0
Accepted
time: 0ms
memory: 4104kb

input:

2
2 1

output:

No
Yes
1 

result:

ok n=2, yes=1, no=1

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 4084kb

input:

11
4 3 6 1 11 10 5 7 8 9 2
11 6 5 1 10 3 8 2 7 9 4
5 9 2 11 3 4 1 10 8 6 7
9 11 8 3 5 4 1 6 7 10 2
3 9 7 6 5 10 1 4 11 8 2
8 2 4 1 5 9 3 7 6 10 11
3 8 2 9 1 4 5 10 11 6 7
10 11 4 1 7 5 2 6 8 9 3
10 6 9 3 2 1 4 8 11 7 5
8 11 9 1 4 10 2 5 3 7 6

output:

Yes
1 2 3 4 5 6 7 8 9 
No
No
No
No
No
No
Yes
1 2 3 4 6 7 8 9 10 
Yes
1 2 3 4 5 6 7 8 9 10 
Yes
1 2 3 5 6 7 9 10 
No

result:

wrong output format Expected integer, but "No" found