QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#578905 | #7861. Inverse Topological Sort | zqx | AC ✓ | 56ms | 29768kb | C++23 | 2.5kb | 2024-09-20 22:40:39 | 2024-09-20 22:40:39 |
Judging History
你现在查看的是测评时间为 2024-09-20 22:40:39 的历史记录
- [2024-11-22 19:52:53]
- hack成功,自动添加数据
- (/hack/1241)
- [2024-09-20 22:40:39]
- 提交
answer
#include<bits/stdc++.h>
#define AC return 0;
#define int long long
#define pii pair<int,int>
#define all(tar) tar.begin(),tar.end()
const int N=1e5+5;
const int mod=998244353;
using namespace std;
int n,m,t;
int a[N],b[N],deg[N],tdeg[N],res[N];
vector<int>e[N];
priority_queue<int>q;
priority_queue<int,vector<int>,greater<int>>p;
bool toposort1(){
int id=0;
for(int i=1;i<=n;i++){
if(tdeg[i]==0){
q.push(i);
}
}
while(q.size()){
int u=q.top();q.pop();
res[++id]=u;
for(auto v:e[u]){
if(--tdeg[v]==0){
q.push(v);
}
}
}
if(id!=n) return false;
for(int i=1;i<=n;i++){
if(res[i]!=b[i]) return false;
}
return true;
}
bool toposort2(){
int id=0;
for(int i=1;i<=n;i++){
if(tdeg[i]==0){
p.push(i);
}
}
while(p.size()){
int u=p.top();p.pop();
res[++id]=u;
for(auto v:e[u]){
if(--tdeg[v]==0){
p.push(v);
}
}
}
if(id!=n) return false;
for(int i=1;i<=n;i++){
if(res[i]!=a[i]) return false;
}
return true;
}
vector<pair<int,int>>ans;
int vis[N];
void dfs(int u){
vis[u]=1;
for(auto j:e[u]){
ans.push_back({u,j});
if(vis[j]) continue;
dfs(j);
}
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
stack<int>st;
for(int i=1;i<=n;i++){
while(!st.empty()&&a[st.top()]<a[i])st.pop();
if(!st.empty())e[a[st.top()]].push_back(a[i]),deg[a[i]]++;
st.push(i);
}
while(!st.empty())st.pop();
for(int i=1;i<=n;i++){
while(!st.empty()&&b[st.top()]>b[i])st.pop();
if(!st.empty())e[b[st.top()]].push_back(b[i]),deg[b[i]]++;
st.push(i);
}
for(int i=1;i<=n;i++) tdeg[i]=deg[i];
bool f1=toposort1();
for(int i=1;i<=n;i++) tdeg[i]=deg[i];
bool f2=toposort2();
if(f1&&f2){
cout<<"Yes\n";
for(int i=1;i<=n;i++){
if(deg[i]==0) dfs(i);
}
cout<<ans.size()<<'\n';
for(auto [x,y]:ans){
cout<<x<<" "<<y<<'\n';
}
}
else{
cout<<"No\n";
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//q.push(1);q.push(2);p.push(1);p.push(2);
//cout<<q.top()<<" "<<p.top()<<endl;
int T=1;
//cin>>T;
while(T--) solve();
AC
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7860kb
input:
3 1 2 3 1 2 3
output:
Yes 2 1 2 2 3
result:
ok n=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 9772kb
input:
3 1 2 3 3 2 1
output:
Yes 0
result:
ok n=3
Test #3:
score: 0
Accepted
time: 0ms
memory: 9940kb
input:
3 3 2 1 1 2 3
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 1ms
memory: 7600kb
input:
10 6 8 9 4 1 3 7 5 10 2 8 6 9 10 4 7 5 3 2 1
output:
Yes 10 6 9 9 4 4 1 4 3 4 7 7 5 4 5 9 7 9 10 10 2
result:
ok n=10
Test #5:
score: 0
Accepted
time: 1ms
memory: 7644kb
input:
10 4 2 5 6 7 8 9 1 3 10 8 7 9 6 5 4 2 1 10 3
output:
Yes 6 4 2 7 9 9 1 1 10 1 3 9 3
result:
ok n=10
Test #6:
score: 0
Accepted
time: 1ms
memory: 9760kb
input:
100 5 16 25 26 36 28 42 46 2 38 48 23 29 30 31 12 40 51 58 64 71 75 83 14 68 74 79 84 86 88 56 6 39 92 9 11 4 47 3 13 15 8 49 54 32 45 61 33 66 72 80 24 69 89 21 82 93 94 27 76 90 10 18 77 78 57 95 7 50 81 96 97 35 19 44 20 55 63 34 60 67 22 73 52 87 91 65 43 85 37 62 53 98 1 41 70 99 59 100 17 92 8...
output:
Yes 148 16 71 25 75 26 28 36 28 46 2 2 86 2 40 40 47 47 3 3 91 91 65 65 43 91 85 85 37 85 62 62 53 3 85 3 78 78 57 78 100 100 17 3 65 3 62 3 57 3 53 3 43 3 37 3 20 20 59 3 17 47 13 47 15 15 8 8 94 94 27 27 90 90 10 10 77 90 18 90 77 90 78 27 55 94 76 94 90 94 99 99 59 8 87 8 76 8 35 35 19 19 67 67 2...
result:
ok n=100
Test #7:
score: 0
Accepted
time: 1ms
memory: 9740kb
input:
1000 11 2 29 50 53 54 155 162 211 213 223 240 270 226 243 276 288 304 315 341 249 358 359 381 178 402 51 417 434 163 459 466 471 498 327 464 518 527 549 559 113 581 589 60 347 594 504 593 598 603 607 610 619 648 649 658 681 684 416 686 153 712 575 741 349 382 759 322 17 289 763 764 774 718 777 9 637...
output:
Yes 1830 11 2 2 901 2 762 2 598 598 790 790 78 78 63 63 980 980 278 278 250 980 354 354 465 465 319 465 558 558 180 180 981 354 460 460 252 252 494 494 356 356 34 252 356 252 302 460 625 625 79 79 224 79 189 189 578 578 237 189 237 625 189 625 224 625 441 441 917 917 244 917 872 441 872 625 578 625 ...
result:
ok n=1000
Test #8:
score: 0
Accepted
time: 38ms
memory: 14576kb
input:
100000 1 5 10 12 13 14 16 17 18 19 21 27 28 33 37 40 41 44 45 49 50 51 52 54 57 58 62 64 67 69 71 72 74 75 77 78 79 80 84 89 93 95 96 100 102 104 111 113 115 117 118 119 120 121 122 123 124 126 127 129 132 135 136 138 139 142 144 150 151 152 153 154 155 156 164 166 167 170 174 177 178 180 181 182 18...
output:
Yes 78810 1 17591 10 52585 52585 62665 10 52401 12 72683 12 56242 12 9486 13 88560 16 79923 16 77358 16 60003 60003 31508 16 31508 17 67167 18 65533 18 41191 18 40557 18 648 28 89241 89241 7737 7737 95692 28 7737 40 99843 44 77231 44 49062 44 41209 41209 54534 44 27643 44 10571 49 95678 95678 55286 ...
result:
ok n=100000
Test #9:
score: 0
Accepted
time: 56ms
memory: 18856kb
input:
100000 40 84 102 116 124 157 177 191 193 199 256 259 293 300 304 326 430 439 473 477 489 511 515 518 547 583 593 630 664 697 747 751 769 787 789 892 928 945 963 971 978 1052 1063 1067 1077 1080 1088 1101 1136 1143 1172 1180 1198 1274 1312 1359 1361 1380 1382 1404 1414 1428 1435 1466 1475 1497 1517 1...
output:
Yes 183695 40 94013 94013 96394 96394 21940 21940 53917 21940 47763 47763 75336 75336 5513 47763 69844 96394 47763 96394 75336 40 91673 91673 6830 6830 90464 90464 92533 92533 78651 92533 95258 95258 31889 31889 5605 5605 36283 31889 29006 29006 96207 96207 20976 29006 86507 29006 75855 75855 21260 ...
result:
ok n=100000
Test #10:
score: 0
Accepted
time: 22ms
memory: 12200kb
input:
100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102...
output:
Yes 1988 28 25410 43 29010 44 85590 50 3874 51 75818 257 2501 386 65575 473 5377 526 40026 547 86971 567 23179 568 35479 612 91704 712 45430 714 36371 765 27333 869 11574 996 42158 1031 80047 1105 60132 1160 14694 1249 4184 1258 98667 1338 29021 1339 42912 1377 87865 1426 76875 1536 58201 1577 1183 ...
result:
ok n=100000
Test #11:
score: 0
Accepted
time: 43ms
memory: 14772kb
input:
100000 4 6 12 16 20 23 24 27 32 34 36 39 46 54 68 76 77 81 86 88 95 99 103 107 112 113 117 120 125 140 142 143 149 158 161 167 171 174 176 187 190 192 195 198 200 206 207 211 217 222 226 227 231 233 239 240 241 245 247 249 264 274 275 276 277 280 288 290 296 303 305 312 321 329 333 336 338 339 341 3...
output:
Yes 122343 6 90079 90079 59182 59182 42488 6 59182 6 52305 6 42488 6 26403 12 71044 12 54141 12 33281 16 88441 16 62781 16 29214 29214 95697 95697 59916 29214 59916 16 6184 6184 94180 6184 55802 55802 871 871 73267 73267 84143 871 28341 55802 12200 12200 6163 6163 84655 55802 14759 55802 28341 55802...
result:
ok n=100000
Test #12:
score: 0
Accepted
time: 34ms
memory: 13260kb
input:
100000 1 2 4 5 6 7 10 13 14 15 16 20 21 22 24 25 26 28 29 30 31 33 34 35 36 37 38 39 40 43 44 45 46 47 48 51 52 55 56 57 58 59 62 65 66 67 68 69 70 71 72 73 74 75 76 77 78 80 81 82 85 87 89 91 92 93 94 97 98 99 100 101 102 103 104 105 106 107 111 112 113 115 117 119 120 121 123 124 128 130 132 133 1...
output:
Yes 44465 10 15024 13 95895 13 72446 72446 8377 13 50166 13 29204 13 25354 25354 52274 13 8377 26 47772 47772 33568 26 47561 26 33568 33 18117 35 76958 35 68646 68646 86483 39 63164 43 77968 43 57505 46 83128 83128 50623 46 56478 56478 19767 19767 75892 56478 35061 46 50623 46 35061 46 19767 47 9760...
result:
ok n=100000
Test #13:
score: 0
Accepted
time: 55ms
memory: 17528kb
input:
100000 33 43 47 65 67 82 88 95 96 113 130 133 140 232 262 266 282 286 298 299 303 324 326 342 352 354 356 359 362 363 364 369 392 398 408 435 442 454 460 489 508 518 537 556 572 574 580 592 613 616 629 650 652 674 684 718 721 724 732 734 801 809 819 831 845 853 856 878 879 895 897 935 946 956 958 96...
output:
Yes 167027 33 94732 94732 21746 21746 98144 98144 17764 21746 94538 94538 98791 98791 24453 21746 85337 85337 54093 54093 59981 21746 80851 21746 61579 61579 65064 65064 36431 36431 90511 65064 44194 44194 75788 21746 51676 21746 49499 21746 47883 47883 36961 36961 91545 36961 90562 90562 39942 3994...
result:
ok n=100000
Test #14:
score: 0
Accepted
time: 43ms
memory: 29768kb
input:
100000 38535 3433 18670 53850 31420 79252 3155 90709 7043 47690 20905 66663 16655 77812 19606 78158 23549 54025 44700 24119 42542 85555 31117 68856 35627 37419 26767 46031 72252 71511 80835 47732 77030 61434 51792 98165 71334 70644 79996 87007 93335 56112 86306 3040 10776 30683 80961 96794 12323 656...
output:
Yes 199973 38535 3433 3433 18670 18670 53850 53850 31420 31420 79252 79252 3155 3155 90709 90709 7043 7043 47690 47690 20905 20905 66663 66663 16655 16655 77812 77812 19606 19606 78158 78158 23549 23549 54025 54025 44700 44700 24119 24119 42542 42542 85555 85555 31117 31117 68856 68856 35627 35627 3...
result:
ok n=100000
Test #15:
score: 0
Accepted
time: 10ms
memory: 11896kb
input:
100000 1 5 7 8 24 29 32 36 39 41 43 44 46 47 52 54 56 58 59 64 68 69 70 73 75 77 79 82 84 86 88 90 92 93 95 98 99 101 102 104 105 108 112 114 115 116 118 123 126 127 128 133 134 139 140 143 145 147 152 153 154 156 160 161 163 165 169 170 176 178 179 180 184 186 187 188 192 193 195 199 200 204 205 20...
output:
No
result:
ok n=100000
Test #16:
score: 0
Accepted
time: 13ms
memory: 12120kb
input:
100000 1 3 4 7 10 11 13 17 18 19 21 22 25 27 28 29 31 35 36 37 38 42 49 50 53 56 57 58 60 62 63 64 68 70 71 79 80 82 83 85 86 87 88 90 93 94 98 103 105 109 110 111 112 116 121 123 127 134 138 139 142 143 148 151 154 156 158 159 160 162 164 166 168 171 172 173 174 175 176 177 180 184 186 187 189 193 ...
output:
No
result:
ok n=100000
Test #17:
score: 0
Accepted
time: 18ms
memory: 11436kb
input:
100000 1 2 8 9 11 14 19 21 22 24 25 28 33 34 35 36 43 49 51 55 57 59 62 64 68 69 70 71 72 75 76 78 79 80 81 82 83 87 88 89 91 92 98 99 105 106 107 111 112 116 118 123 124 125 128 131 133 138 139 141 142 143 146 147 152 154 155 159 161 162 163 164 165 169 172 173 174 175 179 183 184 185 186 187 190 1...
output:
No
result:
ok n=100000
Test #18:
score: 0
Accepted
time: 21ms
memory: 12780kb
input:
100000 60 134 140 182 208 256 291 327 364 395 404 419 439 444 457 469 486 510 527 561 569 595 611 612 645 654 710 778 792 794 810 832 873 890 900 901 911 914 942 946 978 1022 1057 1060 1083 1094 1095 1146 1154 1155 1280 1323 1336 1368 1379 1388 1395 1480 1500 1509 1548 1573 1580 1597 1601 1622 1629 ...
output:
No
result:
ok n=100000
Test #19:
score: 0
Accepted
time: 7ms
memory: 13344kb
input:
100000 52072 2 3 50731 5 75525 49404 8 52753 2744 11 34189 13 48355 15 16 17 50376 86416 20 21 56114 23 20072 25 53838 48273 63338 29 30 60156 6205 8084 34 35 36 48381 71655 72484 63969 88506 59722 27083 5369 44672 86160 39926 48 49 8962 51 47113 53 69142 55 66271 24245 74454 59 72556 61 35930 86895...
output:
No
result:
ok n=100000
Test #20:
score: 0
Accepted
time: 17ms
memory: 12744kb
input:
100000 13821 33496 19412 85158 61916 61576 41795 39637 42402 12256 37931 7198 19499 24983 15918 19942 56948 7239 17886 24328 17628 63213 4681 90112 37749 17984 25778 75577 33274 43479 47779 64385 77793 82833 15116 96895 87829 30340 25506 7179 48585 77809 44101 91839 93597 69594 37840 3271 4541 68178...
output:
No
result:
ok n=100000
Test #21:
score: 0
Accepted
time: 0ms
memory: 9688kb
input:
1 1 1
output:
Yes 0
result:
ok n=1
Extra Test:
score: 0
Extra Test Passed