QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#218282 | #6550. Elimination Race | zhouhuanyi | TL | 691ms | 5860kb | C++14 | 2.3kb | 2023-10-17 22:38:35 | 2023-10-17 22:38:35 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<bitset>
#include<vector>
#define N 500
#define M 1000
#define K 2000000
using namespace std;
const int inf=(int)(1e9);
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int n,s,t,leng,tong[N+1],ps[N+1],cl[N+1],in[N+1],p[N+1],sp[N+1],a[N+1][N+1],rk[N+1][N+1];
bool used[M+1],vis[M+1];
bitset<N+1>B[N+1];
bitset<N+1>B2[N+1];
bitset<N+1>useds;
vector<int>E[N+1];
bool dfs(int x)
{
for (int i=(B[x]&useds)._Find_first();i!=B[x].size();i=(B[x]&useds)._Find_next(i))
{
useds[i]=0;
if (!p[i]||dfs(p[i]))
{
p[i]=x;
return 1;
}
}
return 0;
}
void topo_sort()
{
int top;
queue<int>q;
for (int i=1;i<=n-1;++i) E[i].clear(),in[i]=0;
for (int i=1;i<=n-1;++i)
for (int j=1;j<=n-1;++j)
if (rk[j][sp[i]]>rk[j][sp[j]])
E[i].push_back(j),in[j]++;
for (int i=1;i<=n-1;++i)
if (!in[i])
q.push(i);
while (!q.empty())
{
top=q.front(),q.pop(),tong[++leng]=top;
for (int i=0;i<E[top].size();++i)
{
in[E[top][i]]--;
if (!in[E[top][i]]) q.push(E[top][i]);
}
}
return;
}
int main()
{
int res,x,y;
n=read();
for (int i=1;i<=n-1;++i)
for (int j=1;j<=n;++j)
a[i][j]=read(),rk[i][a[i][j]]=j;
for (int i=1;i<=n;++i)
{
res=leng=0;
for (int j=1;j<=n;++j) B[j].reset(),p[j]=0;
for (int j=1;j<=n-1;++j)
for (int k=rk[j][i]+1;k<=n;++k)
B[j][a[j][k]]=1;
for (int j=1;j<=n-1;++j)
{
useds.set();
if (dfs(j)) res++;
else break;
}
if (res==n-1)
{
puts("Yes");
for (int j=1;j<=(n<<1);++j) vis[j]=0;
for (int j=1;j<=n-1;++j) ps[j]=n;
while (1)
{
x=0;
for (int j=1;j<=n-1;++j)
if (!vis[j])
{
x=j;
break;
}
if (!x) break;
for (int j=1;j<=n-1;++j)
if (!vis[j])
{
while (vis[n-1+a[j][ps[j]]]) ps[j]--;
cl[j]=a[j][ps[j]];
}
for (int j=1;j<=n-1;++j) used[j]=0;
while (!used[x]) used[x]=1,x=p[cl[x]];
y=x;
do
{
sp[y]=cl[y],vis[y]=vis[n-1+cl[y]]=1,y=p[cl[y]];
}
while (x!=y);
}
topo_sort();
for (int j=1;j<=n-1;++j) printf("%d ",tong[j]);
puts("");
}
else puts("No");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
input:
4 1 2 3 4 2 1 3 4 4 3 1 2
output:
Yes 2 3 1 No No No
result:
ok n=4, yes=1, no=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3652kb
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: 3696kb
input:
2 1 2
output:
Yes 1 No
result:
ok n=2, yes=1, no=1
Test #4:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
2 2 1
output:
No Yes 1
result:
ok n=2, yes=1, no=1
Test #5:
score: 0
Accepted
time: 1ms
memory: 3728kb
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 6 7 8 9 10 4 3 5 2 No No No No No No Yes 2 5 6 7 8 9 1 4 3 10 Yes 1 2 6 7 8 9 4 5 3 10 Yes 2 3 4 6 9 7 1 5 10 8 No
result:
ok n=11, yes=4, no=7
Test #6:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
11 6 7 8 9 3 4 1 11 5 10 2 7 10 6 3 1 2 5 11 4 9 8 4 3 9 1 10 2 5 7 6 8 11 10 4 2 11 8 1 5 7 9 6 3 11 9 4 6 8 2 1 7 3 5 10 9 10 2 7 4 11 6 1 3 8 5 11 8 4 9 7 1 2 10 5 3 6 5 7 9 10 1 8 4 2 6 11 3 4 2 9 7 10 1 6 8 3 5 11 2 7 6 10 5 11 1 8 4 9 3
output:
Yes 1 2 5 6 7 9 10 3 4 8 No No Yes 1 5 7 10 8 9 6 2 3 4 No No Yes 1 2 3 5 6 7 9 4 8 10 No Yes 1 2 3 5 10 9 4 7 8 6 No No
result:
ok n=11, yes=4, no=7
Test #7:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
11 3 5 9 7 4 1 8 11 10 2 6 9 7 10 4 8 3 1 6 5 2 11 9 5 11 3 8 7 1 6 2 4 10 8 9 11 1 4 3 10 6 7 2 5 11 3 7 8 5 9 1 2 10 6 4 8 3 10 11 1 4 2 5 6 7 9 5 9 10 2 4 3 7 1 11 6 8 11 8 10 3 5 7 4 1 2 6 9 7 8 1 9 10 5 3 11 2 6 4 2 4 6 9 5 11 7 1 8 10 3
output:
Yes 2 3 4 7 8 9 10 6 5 1 No No No No No Yes 1 2 3 4 6 7 9 10 8 5 No No No No
result:
ok n=11, yes=2, no=9
Test #8:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
11 3 5 9 2 11 1 4 8 6 10 7 8 3 4 9 1 5 6 2 7 10 11 10 6 4 7 11 9 1 3 5 8 2 9 3 2 7 8 4 5 10 1 11 6 3 4 9 10 1 8 2 7 6 11 5 9 4 7 8 1 11 6 3 5 2 10 5 11 4 10 6 3 2 1 9 8 7 10 11 8 5 2 1 9 7 4 6 3 6 3 8 9 4 11 1 2 10 7 5 8 3 11 10 9 1 6 5 7 2 4
output:
Yes 3 4 6 8 9 10 5 2 1 7 No No No No No No Yes 3 4 7 8 10 1 6 5 9 2 Yes 1 3 4 8 9 10 7 5 2 6 No No
result:
ok n=11, yes=3, no=8
Test #9:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
11 3 5 7 10 9 6 2 1 11 8 4 3 6 1 7 5 11 4 10 9 8 2 10 4 6 7 11 3 1 2 9 5 8 10 4 1 9 11 5 3 8 6 7 2 11 5 9 1 10 4 8 6 7 2 3 3 2 7 9 11 10 1 5 8 4 6 4 5 11 8 6 7 10 1 2 3 9 2 7 3 11 8 1 9 6 4 10 5 4 8 2 7 5 10 6 1 11 3 9 9 6 3 5 1 10 11 7 8 4 2
output:
Yes 6 9 10 7 2 4 3 5 8 1 No No No No No Yes 4 5 6 10 1 2 3 7 9 8 No No Yes 1 3 6 8 10 2 9 5 7 4 Yes 1 5 6 9 10 2 4 7 3 8
result:
ok n=11, yes=4, no=7
Test #10:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
11 6 5 11 2 8 9 7 10 1 4 3 11 4 3 6 10 7 9 1 8 5 2 3 2 6 8 5 7 9 1 10 4 11 11 6 9 1 3 10 4 2 7 8 5 5 6 8 7 11 9 1 3 4 2 10 6 5 3 9 2 1 10 11 8 4 7 9 3 4 6 2 1 5 7 8 10 11 11 6 9 8 1 4 3 2 5 10 7 6 4 7 11 3 2 1 5 8 10 9 10 3 8 6 4 1 11 7 9 2 5
output:
No No No Yes 1 2 3 5 6 9 8 4 10 7 No Yes 1 2 3 4 8 9 7 6 10 5 No Yes 1 2 4 6 7 9 8 3 5 10 No No No
result:
ok n=11, yes=3, no=8
Test #11:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
11 10 5 4 6 11 1 3 7 9 8 2 2 8 10 4 6 1 7 9 3 11 5 5 7 11 8 3 1 9 2 4 10 6 5 6 11 10 3 1 2 9 8 4 7 6 3 4 9 11 5 1 2 8 10 7 8 7 6 1 10 3 5 11 9 4 2 5 11 9 4 6 2 7 1 8 3 10 10 11 2 1 9 4 3 5 8 6 7 9 3 4 6 5 1 11 8 2 7 10 7 10 4 5 9 6 8 1 3 11 2
output:
Yes 2 3 7 10 9 4 5 1 8 6 No Yes 2 5 7 10 8 1 6 9 3 4 Yes 3 4 6 7 1 10 5 9 8 2 No No No Yes 1 2 5 9 4 8 7 3 6 10 Yes 2 4 8 3 7 9 1 6 10 5 No Yes 2 3 5 9 10 4 8 7 6 1
result:
ok n=11, yes=6, no=5
Test #12:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
11 7 8 4 5 1 3 6 9 11 10 2 8 10 9 7 1 3 5 4 2 11 6 4 11 9 5 3 1 2 10 8 6 7 9 6 7 1 3 8 2 4 10 5 11 9 3 10 2 4 1 6 7 5 11 8 9 3 1 7 2 6 5 8 11 4 10 2 4 9 3 1 5 11 6 7 8 10 3 4 11 10 8 6 1 5 2 7 9 4 11 7 6 8 1 10 9 3 5 2 8 7 4 9 10 3 1 5 2 6 11
output:
Yes 1 3 4 5 7 8 10 2 6 9 No Yes 1 2 3 4 5 7 8 9 6 10 Yes 2 3 4 5 6 9 1 8 10 7 Yes 4 5 6 8 9 10 7 1 2 3 No No No No No No
result:
ok n=11, yes=4, no=7
Test #13:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
11 4 8 10 9 6 3 1 5 2 7 11 10 8 7 4 9 1 6 11 3 2 5 3 10 11 6 1 4 5 2 7 9 8 4 9 8 3 1 6 11 7 5 2 10 8 2 11 7 3 1 5 6 10 4 9 4 9 3 6 5 1 7 10 11 2 8 4 3 6 7 1 5 8 2 9 11 10 10 7 4 1 9 8 2 3 6 11 5 10 7 2 8 5 1 11 6 4 3 9 7 6 9 8 1 11 5 4 2 3 10
output:
Yes 1 2 3 4 5 8 10 7 9 6 Yes 1 2 4 6 8 7 10 3 9 5 Yes 1 2 3 9 10 8 6 5 4 7 Yes 1 2 3 5 10 8 6 9 4 7 No Yes 4 5 6 8 7 3 1 2 9 10 Yes 1 4 6 8 3 5 7 9 2 10 No No No No
result:
ok n=11, yes=6, no=5
Test #14:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
11 8 5 9 7 6 1 10 4 2 3 11 3 6 5 11 9 7 1 2 4 10 8 2 11 3 8 1 6 7 5 4 10 9 7 5 8 6 4 9 1 2 3 10 11 6 7 8 1 2 3 11 9 10 5 4 7 4 10 9 1 2 8 5 11 3 6 10 7 5 6 11 3 1 2 9 4 8 5 2 6 8 10 1 9 3 4 7 11 5 7 3 11 8 2 1 6 9 4 10 2 3 10 4 1 11 5 7 8 9 6
output:
Yes 2 3 4 6 9 7 1 8 10 5 Yes 1 2 6 4 8 9 5 7 10 3 Yes 1 2 3 6 4 8 7 5 10 9 No Yes 3 5 7 8 10 4 6 9 1 2 No Yes 2 3 8 10 7 4 6 5 9 1 No No No No
result:
ok n=11, yes=5, no=6
Test #15:
score: 0
Accepted
time: 673ms
memory: 5860kb
input:
500 446 156 267 294 482 398 430 13 311 318 474 426 140 484 83 387 257 136 69 305 295 283 287 55 52 65 322 249 43 56 331 443 226 214 341 182 389 464 84 477 187 40 327 411 248 10 223 165 379 293 12 9 5 230 309 367 2 397 265 59 361 118 196 316 390 213 194 167 483 452 114 345 263 219 87 94 160 224 200 2...
output:
Yes 2 3 5 6 8 12 15 16 17 18 19 27 29 30 31 32 33 35 38 39 41 42 43 46 48 49 50 51 52 53 55 56 58 59 63 64 65 67 68 69 71 73 74 76 77 80 82 84 85 86 87 88 89 91 92 93 97 102 103 104 106 108 109 111 113 118 121 123 124 128 129 131 132 133 135 137 138 139 143 144 145 146 149 150 151 152 153 155 156 15...
result:
ok n=500, yes=171, no=329
Test #16:
score: 0
Accepted
time: 691ms
memory: 5860kb
input:
500 18 271 51 335 212 326 93 264 408 66 230 181 456 149 259 396 269 443 136 446 250 409 240 457 319 289 402 334 247 216 106 214 468 448 58 186 137 225 337 487 281 333 130 275 169 420 100 71 57 284 63 454 108 375 164 437 133 110 440 350 479 370 276 211 193 148 198 222 496 460 308 85 286 242 257 435 4...
output:
Yes 2 5 6 9 11 12 14 17 18 21 23 25 26 27 28 30 34 37 38 40 41 44 45 46 47 48 54 55 57 61 63 64 66 67 69 70 74 78 79 80 81 82 84 88 89 90 92 94 98 99 100 103 105 107 108 110 113 114 115 116 117 120 121 122 130 132 138 142 145 146 148 150 151 154 157 158 165 167 170 171 172 173 177 178 179 182 183 18...
result:
ok n=500, yes=185, no=315
Test #17:
score: -100
Time Limit Exceeded
input:
500 24 261 411 242 116 202 460 6 169 140 268 333 447 468 341 373 58 274 175 180 77 232 465 326 300 211 204 75 98 425 322 90 408 489 227 480 89 31 94 248 334 299 76 290 157 178 111 143 103 117 131 292 456 201 118 285 150 10 56 251 418 448 453 47 451 184 343 42 210 68 113 422 165 391 415 272 45 82 490...
output:
Yes 8 10 11 12 13 19 20 21 24 27 28 29 30 31 32 34 37 38 40 44 46 49 50 52 54 55 56 57 62 63 64 65 68 69 71 72 79 80 83 84 85 86 87 90 91 92 93 94 97 101 103 106 107 109 110 112 113 115 117 120 124 126 129 131 136 139 143 144 146 149 151 153 154 155 156 158 159 160 162 163 164 167 168 171 172 174 17...