QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#217397 | #6550. Elimination Race | 275307894a | WA | 0ms | 4104kb | C++14 | 2.3kb | 2023-10-16 20:32:42 | 2023-10-16 20:32:44 |
Judging History
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