QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#110406 | #4892. 序列 | AK_Dream | 50 | 16ms | 38576kb | C++14 | 1.8kb | 2023-06-01 21:25:22 | 2023-06-01 21:25:24 |
Judging History
answer
#include <bits/stdc++.h>
#define N 300005
#define pb push_back
using namespace std;
int n, m, c[N], ans[N];
int a[N][3], val[N];
vector<int> V[N], id[2][N], E[N];
int dfn[N], low[N], col[N], stk[N], in[N], tme, top, scc;
inline void adeg(int u, int v) { E[u].pb(v); }
void tarjan(int x) {
dfn[x] = low[x] = ++tme;
stk[++top] = x; in[x] = 1;
for (auto y : E[x]) {
if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
else if (in[y]) low[x] = min(low[x], dfn[y]);
}
if (dfn[x] == low[x]) {
++scc; int z = 0;
do {
z = stk[top--];
col[z] = scc; in[z] = 0;
} while (z != x);
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
for (int j = 0; j <= 2; j++) scanf("%d", &a[i][j]);
scanf("%d", &val[i]);
for (int j = 0; j <= 2; j++) V[a[i][j]].push_back(val[i]);
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
sort(V[i].begin(),V[i].end());
c[i] = V[i].size();
for (int j = 0; j < c[i]; j++) {
id[0][i].pb(++cnt); id[1][i].pb(++cnt);
if (j) adeg(id[0][i][j-1],id[0][i][j]), adeg(id[1][i][j],id[1][i][j-1]);
}
}
for (int i = 1; i <= m; i++) {
for (int p:{0,1,2}) for (int q:{0,1,2}) if (p != q) {
int u = a[i][p], v = a[i][q];
int up = lower_bound(V[u].begin(),V[u].end(),val[i])-V[u].begin();
int vp = lower_bound(V[v].begin(),V[v].end(),val[i])-V[v].begin();
adeg(id[0][u][up], id[1][v][vp]);
if (up+1<c[u] && vp+1<c[v]) adeg(id[1][u][up+1],id[0][v][vp+1]);
}
}
for (int i = 1; i <= cnt; i++) if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++) {
ans[i] = 1;
for (int j = 0; j < c[i]; j++) {
int u = id[0][i][j], v = id[1][i][j];
if (col[u] == col[v]) { puts("NO"); return 0; }
if (col[v] < col[u]) ans[i] = V[i][j];
}
}
puts("YES");
for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 2ms
memory: 31968kb
input:
10 10 6 3 10 133562624 8 7 6 685486592 4 2 7 332482851 10 8 9 211550017 2 10 1 165556251 10 8 5 211550017 6 8 2 332482851 4 9 2 332482851 8 1 4 193658790 9 6 10 728674154
output:
YES 165556251 332482851 1 193658790 211550017 728674154 685486592 211550017 728674154 133562624
result:
ok solution is correct
Test #2:
score: 0
Accepted
time: 7ms
memory: 33244kb
input:
10 9 5 3 7 489042696 10 9 3 489042696 5 9 4 589265757 1 3 7 489042696 9 3 10 489042696 2 8 7 402617168 2 4 5 564742148 1 8 3 615037121 2 8 4 564742148
output:
YES 615037121 402617168 489042696 564742148 589265757 1 402617168 615037121 589265757 489042696
result:
ok solution is correct
Test #3:
score: 0
Accepted
time: 8ms
memory: 33476kb
input:
9 9 3 8 4 385329352 1 4 5 826490084 4 5 9 866319564 2 4 1 449825973 8 3 5 385329352 6 2 9 88759441 3 6 9 88759441 6 8 9 385329352 4 8 1 449825973
output:
YES 449825973 88759441 1 866319564 826490084 88759441 1 385329352 866319564
result:
ok solution is correct
Test #4:
score: 0
Accepted
time: 3ms
memory: 33396kb
input:
10 10 1 9 6 957652738 9 7 1 934947905 9 10 8 507132050 5 2 8 162855738 2 2 8 537894544 9 9 9 266667281 3 3 8 158325440 2 7 9 752321309 10 3 1 104743493 4 10 10 799817379
output:
NO
result:
ok no solution
Test #5:
score: 0
Accepted
time: 4ms
memory: 31660kb
input:
8 9 7 4 7 187362209 5 1 1 634248682 2 3 2 664513540 3 2 4 161388361 5 1 3 463648080 8 1 6 485087787 6 3 6 689280466 3 6 8 116609606 7 2 7 399054929
output:
NO
result:
ok no solution
Test #6:
score: 0
Accepted
time: 9ms
memory: 32792kb
input:
10 8 5 6 10 861588864 10 1 8 608002433 8 3 4 196795234 1 8 3 285047219 9 7 5 480962478 6 10 1 780552157 3 4 2 190713929 7 5 6 780552157
output:
YES 285047219 1 196795234 190713929 861588864 780552157 480962478 608002433 480962478 861588864
result:
ok solution is correct
Test #7:
score: 0
Accepted
time: 9ms
memory: 33028kb
input:
10 5 6 5 1 644007358 4 2 1 644007358 8 5 1 672067709 7 2 1 845787134 9 8 5 672067709
output:
YES 1 845787134 1 644007358 672067709 644007358 845787134 672067709 672067709 1
result:
ok solution is correct
Test #8:
score: 0
Accepted
time: 3ms
memory: 32972kb
input:
9 6 9 6 3 408886589 3 2 1 680261634 8 4 1 540611446 6 3 2 680261634 5 2 1 540611446 7 3 2 680261634
output:
YES 1 680261634 680261634 540611446 540611446 408886589 680261634 540611446 408886589
result:
ok solution is correct
Subtask #2:
score: 0
Dangerous Syscalls
Test #9:
score: 10
Accepted
time: 16ms
memory: 38576kb
input:
40 9880 4 19 31 610502845 10 19 33 190412843 21 24 39 649028784 16 22 40 569593239 5 9 37 550862419 11 23 40 654613112 6 18 23 492267246 22 23 30 538715841 6 16 24 407919735 5 16 18 388907784 2 16 18 388907784 21 24 28 281403057 7 12 27 451830401 3 11 16 508407438 15 33 36 561955959 6 23 29 70605893...
output:
YES 877488996 197498120 508407438 610502845 209356929 706058934 655952999 624132238 550862419 32695410 654613112 72694954 399757770 396827347 561955959 407919735 779328631 388907784 190412843 657895429 832003778 569593239 492267246 32695410 718125822 812463588 451830401 281403057 877488996 538715841...
result:
ok solution is correct
Test #10:
score: -10
Dangerous Syscalls
input:
80 82160 8 15 41 111467584 35 54 58 471689837 51 66 69 545620573 20 63 76 46182451 15 34 40 54922534 19 27 49 410013534 6 13 18 849916477 3 12 30 436881726 8 23 54 239683045 6 37 40 544597112 29 52 70 792746131 7 52 75 478735558 11 50 74 735803963 4 28 50 415323204 23 54 68 347125331 33 67 70 525526...
output:
result:
Subtask #3:
score: 30
Accepted
Dependency #1:
100%
Accepted
Test #16:
score: 30
Accepted
time: 10ms
memory: 32740kb
input:
1000 996 527 924 774 540173899 415 382 71 188751360 884 463 698 125924043 810 890 663 324838547 366 94 515 666179824 192 778 279 847431254 769 80 245 922736826 529 115 418 778769842 446 715 604 875242794 160 625 423 424822525 877 194 974 556338768 198 70 696 237534851 8 304 726 470021479 496 953 866...
output:
YES 1 1 670603801 824109436 194070621 614405181 356247025 420489663 1 950845418 609512045 609512045 857879636 824109436 626441474 607162501 664929448 1 409659940 703780779 640834798 585395354 766586241 441780827 209233215 734690663 439151771 2972186 846644135 169726917 324838547 953642585 1 18163853...
result:
ok solution is correct
Test #17:
score: 0
Accepted
time: 7ms
memory: 33824kb
input:
996 1000 848 457 378 880385818 743 926 806 553228470 619 544 861 974849688 698 389 756 951371810 120 71 828 505821547 318 940 217 549943590 536 852 664 540115645 107 749 796 966841837 905 659 358 596025315 622 988 532 365141303 742 687 206 69113219 830 712 5 484296740 107 473 839 302448568 453 307 7...
output:
NO
result:
ok no solution
Test #18:
score: 0
Accepted
time: 5ms
memory: 32148kb
input:
990 988 723 217 736 529714749 380 396 260 409316596 716 401 619 788977572 232 40 909 164972335 323 646 767 742422834 71 268 229 498183446 695 825 949 605491713 447 539 73 644621097 420 81 160 368595699 425 287 797 536503051 385 36 451 515447677 952 980 356 506411673 149 355 67 955377149 726 594 192 ...
output:
YES 443272028 1 353952887 423457295 1 554132482 1 905142170 166672290 404755886 1 732938991 1 1 458153570 1 577930774 801254851 851220356 393414923 1 886695682 643346815 1 794870892 705435825 942112175 480960502 739916080 681118387 1 420102231 859374472 563299103 873645479 174054456 1 163015569 3539...
result:
ok solution is correct
Test #19:
score: 0
Accepted
time: 8ms
memory: 33116kb
input:
1000 992 358 307 292 715383877 889 622 482 680348743 106 61 16 780021827 967 840 355 799032574 7 6 2 371465877 886 277 143 488646126 196 7 6 325091271 292 274 172 378495286 356 297 226 247061041 298 136 30 288877994 399 191 33 108831408 595 350 48 342498526 406 5 3 666420994 321 146 69 878509167 699...
output:
YES 568892025 371465877 240147313 382659615 912032235 535835515 325091271 506493571 388344702 822893994 719429987 303866276 583326332 589898523 777989666 535270750 36369171 277896857 542030738 560500043 616674702 498011517 889586844 436151328 118249813 335897947 365646875 783512918 494764081 2139625...
result:
ok solution is correct
Test #20:
score: 0
Accepted
time: 6ms
memory: 33276kb
input:
1000 995 93 88 83 205161273 59 54 47 272815050 976 968 967 128081945 491 486 476 163208281 964 960 953 393463398 126 122 119 919973605 251 243 241 268012077 401 398 390 888396262 786 777 773 821327852 264 256 250 387688185 107 104 95 764563667 198 195 185 421528348 18 14 4 465222052 163 154 149 4425...
output:
YES 465222052 1 420272005 465222052 420272005 725814201 465222052 554351793 757386571 554351793 290177907 465222052 164869035 465222052 578945293 725814201 574834092 774812229 508474159 527586554 465222052 475145071 574834092 854236804 757386571 508474159 164869035 305048016 508663785 225265468 8591...
result:
ok solution is correct
Test #21:
score: 0
Accepted
time: 7ms
memory: 33452kb
input:
1000 1000 556 922 96 247240976 370 478 526 363454712 150 642 778 518784471 643 799 624 143452980 802 129 973 753138409 199 215 390 501598040 583 526 122 48846823 854 611 985 605244939 49 338 443 128617908 273 232 409 244385789 653 658 559 488952689 407 210 464 433805586 585 90 940 614614430 200 884 ...
output:
NO
result:
ok no solution
Test #22:
score: 0
Accepted
time: 5ms
memory: 33216kb
input:
1000 998 629 816 724 126263144 621 897 391 796546541 696 322 185 803804896 305 790 889 153079778 330 652 692 609221623 253 703 517 578803480 537 563 346 245597626 231 706 863 483185655 480 852 407 473711558 156 1 967 762984005 842 945 498 943018627 513 799 78 86152666 703 517 550 578803480 168 506 9...
output:
YES 535370966 653909866 527164019 875149419 704759861 576529855 159013463 545426727 693134038 1 1 1 537710478 906800639 1 1 756105032 461649456 603236285 603236285 1 459871381 864400294 505777059 305616160 727284214 642678444 642678444 1 1 438990328 686449440 886970129 485922269 1 1 1 454273855 1 42...
result:
ok solution is correct
Test #23:
score: 0
Accepted
time: 10ms
memory: 32644kb
input:
1000 997 357 347 345 733358338 682 672 663 209734493 393 387 380 305734825 627 626 625 324357526 928 919 914 438604806 625 616 610 417853070 540 537 531 807315869 886 885 878 777205250 752 750 748 348526994 679 678 675 276712558 970 969 961 376456558 518 516 506 571223812 264 256 255 562733931 23 20...
output:
YES 997630534 997630534 1 666922803 787030151 251259941 787030151 410528085 284506465 666922803 785449789 785449789 375712613 251259941 251259941 251259941 301736605 410528085 666922803 187474183 138591831 284506465 449165229 483096393 301736605 885066723 369361134 138591831 692315266 187474183 2317...
result:
ok solution is correct
Test #24:
score: 0
Accepted
time: 12ms
memory: 33252kb
input:
1000 998 188 595 689 592674202 126 841 768 505688775 274 1000 351 565885054 767 460 705 439050630 61 626 381 387458774 607 444 978 618476232 264 583 900 850042952 53 722 698 40237254 482 112 552 162817181 242 545 956 648781127 964 186 989 830125903 475 685 786 521769463 841 768 13 478559108 409 443 ...
output:
NO
result:
ok no solution
Test #25:
score: 0
Accepted
time: 5ms
memory: 32236kb
input:
1000 997 224 221 215 685183418 765 756 753 345268843 880 874 871 547734181 796 787 778 764396807 480 470 469 896165180 700 698 690 500019202 450 442 438 667969122 151 146 141 549351752 819 810 804 186861970 537 531 527 310783900 884 881 873 888208832 590 588 583 659624517 152 150 144 323089371 618 6...
output:
NO
result:
ok no solution
Subtask #4:
score: 0
Skipped
Dependency #2:
0%