QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#440122#4892. 序列Kalenist50 13ms20344kbC++202.9kb2024-06-13 09:43:392024-06-13 09:43:39

Judging History

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

  • [2024-06-13 09:43:39]
  • 评测
  • 测评结果:50
  • 用时:13ms
  • 内存:20344kb
  • [2024-06-13 09:43:39]
  • 提交

answer

#include<bits/stdc++.h>
#define N 100010
#define add push_back
#define For(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
int n,m,rnk,tot,dfn[N<<3],top,ans[N];
int a[N],b[N],c[N],v[N],in[N<<3];
int id[N<<2][2],low[N<<3],sta[N<<3];
const int inf=1e9;
bool insta[N<<3],con[N<<2];
vector<int> go[N],h[N],nd[N];
inline void edge(int x,int y){go[x].add(y);}
inline void ckmn(int &x,int y){x=min(x,y);}
inline int read()
{
    register int x=0,c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}

inline int binary(int id,int val)
{
    int l=0,r=h[id].size()-1,res=0;
    while(l <= r)
    {
        int mid=l+r>>1;
        if(h[id][mid] >= val) res=mid,r=mid-1;
        else l=mid+1;
    }
    return res;
}

inline void addedge(int i,int j,int k,int v)
{
    int ri=binary(i,v),rj=binary(j,v),rk=binary(k,v);
    if(ri+1 == h[i].size())
        edge(id[nd[i][ri+1]][1],id[nd[i][ri+1]][0]);
    else 
    {
        edge(id[nd[i][ri+1]][1],id[nd[j][rj+1]][0]);
        edge(id[nd[i][ri+1]][1],id[nd[k][rk+1]][0]);
    }
    if(!ri)
        edge(id[nd[i][ri]][0],id[nd[i][ri]][1]);
    else
    {
        edge(id[nd[i][ri]][0],id[nd[j][rj]][1]);
        edge(id[nd[i][ri]][0],id[nd[k][rk]][1]);
    }
    return;
}

inline void tarjan(int x)
{
    dfn[x]=low[x]=++dfn[0];
    insta[sta[++top]=x]=true;
    for(int to:go[x])
        if(!dfn[to]) tarjan(to),ckmn(low[x],low[to]);
        else if(insta[to]) ckmn(low[x],dfn[to]);
    if(low[x] != dfn[x]) return;
    in[0]++,sta[top+1]=0;
    while(sta[top+1] != x)
    {
        int nw=sta[top--];
        insta[nw]=false,in[nw]=in[0];
    }
    return;
}

int main()
{
    n=read(),m=read();
    For(i,1,m)
    {
        a[i]=read(),b[i]=read(),c[i]=read(),v[i]=read();
        h[a[i]].add(v[i]),h[b[i]].add(v[i]),h[c[i]].add(v[i]);
    }
    For(i,1,n) 
    {
        int sz=h[i].size();
        sort(h[i].begin(),h[i].end());
        For(j,1,sz+1) nd[i].add(++rnk);
    }For(i,1,rnk) id[i][0]=++tot,id[i][1]=++tot;
    For(i,1,m) 
    {
        addedge(a[i],b[i],c[i],v[i]);
        addedge(b[i],a[i],c[i],v[i]);
        addedge(c[i],a[i],b[i],v[i]);
    }
    For(i,1,n) 
    {
        int sz=h[i].size();
        For(j,0,sz-1) edge(id[nd[i][j]][0],id[nd[i][j+1]][0]);
        For(j,1,sz) edge(id[nd[i][j]][1],id[nd[i][j-1]][1]);
    }For(i,1,tot) if(!dfn[i]) tarjan(i);
    For(i,1,rnk) if(in[id[i][0]] == in[id[i][1]]) 
        {puts("NO");return 0;}
    For(i,1,rnk) con[i]=(in[id[i][1]]<in[id[i][0]]);
    For(i,1,n)
    {
        if(h[i].empty()) {ans[i]=20061130;continue;}
        int sz=h[i].size(),pos=0;
        For(j,0,sz-1) if(!con[nd[i][j+1]]) 
            {pos=j;break;}
        ans[i]=h[i][pos];
    }puts("YES");
    For(i,1,n) 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: 0ms
memory: 16120kb

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 133562624 193658790 211550017 728674154 685486592 211550017 728674154 133562624 

result:

ok solution is correct

Test #2:

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

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 20061130 402617168 615037121 589265757 489042696 

result:

ok solution is correct

Test #3:

score: 0
Accepted
time: 4ms
memory: 14088kb

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 88759441 826490084 866319564 88759441 20061130 385329352 866319564 

result:

ok solution is correct

Test #4:

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

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: 13832kb

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: 0ms
memory: 14092kb

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 190713929 190713929 196795234 861588864 780552157 480962478 608002433 480962478 861588864 

result:

ok solution is correct

Test #7:

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

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
644007358 845787134 20061130 644007358 672067709 644007358 845787134 672067709 672067709 20061130 

result:

ok solution is correct

Test #8:

score: 0
Accepted
time: 4ms
memory: 14076kb

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
540611446 680261634 680261634 540611446 540611446 408886589 680261634 540611446 408886589 

result:

ok solution is correct

Subtask #2:

score: 0
Runtime Error

Test #9:

score: 10
Accepted
time: 13ms
memory: 20344kb

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
Runtime Error

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: 0ms
memory: 12612kb

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
221993614 152279174 670603801 824109436 194070621 614405181 356247025 420489663 20061130 950845418 609512045 609512045 918039415 824109436 626441474 607162501 664929448 179490893 409659940 703780779 640834798 585395354 766586241 441780827 209233215 734690663 106200367 2972186 846644135 169726917...

result:

ok solution is correct

Test #17:

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

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: 0ms
memory: 16628kb

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 161058514 353952887 423457295 346754114 554132482 370764537 905142170 166672290 404755886 364522781 732938991 188181844 240197885 458153570 411373341 577930774 801254851 851220356 393414923 253720282 886695682 643346815 491933682 794870892 705435825 942112175 480960502 739916080 681118...

result:

ok solution is correct

Test #19:

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

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 605759246 118249813 335897947 365646875 783512918 494764081 2139625...

result:

ok solution is correct

Test #20:

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

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 20061130 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 2252654...

result:

ok solution is correct

Test #21:

score: 0
Accepted
time: 3ms
memory: 14512kb

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: 0ms
memory: 14508kb

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 420126600 474381167 232744002 537710478 906800639 525031938 305616160 756105032 461649456 603236285 603236285 180028508 459871381 864400294 505777059 305616160 727284214 642678444 642678444 374675169 247334...

result:

ok solution is correct

Test #23:

score: 0
Accepted
time: 6ms
memory: 14744kb

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 20061130 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 1874741...

result:

ok solution is correct

Test #24:

score: 0
Accepted
time: 6ms
memory: 14416kb

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: 0ms
memory: 14336kb

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%