QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#592256#4892. 序列LYLAKIOI60 478ms120208kbC++143.2kb2024-09-26 21:35:442024-09-26 21:35:46

Judging History

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

  • [2024-09-26 21:35:46]
  • 评测
  • 测评结果:60
  • 用时:478ms
  • 内存:120208kb
  • [2024-09-26 21:35:44]
  • 提交

answer

// LUOGU_RID: 178154058
#include<bits/stdc++.h>
#define up(i,l,r) for(int i=(l);i<=(r);++i)
#define down(i,l,r) for(int i=(l);i>=(r);--i)
#define p_b push_back
#define m_p make_pair
#define pi pair<int,int>
#define p1 first
#define p2 second
#define ppc __builtin_popcount
#define nx(a,b) (*st[a].upper_bound(b))
using namespace std;
typedef long long ll;
const int maxn=2e6+10;
const int LIM=60;
const ll inf=1e18;
inline ll read(){
    ll x=0;short t=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int n,m,A[maxn],ct;
set<int>st[maxn];
const int M=1e7;
int hd[maxn],to[M],nxt[M],ect;
int dfn[maxn],low[maxn],stk[maxn],tp,instk[maxn],cc,bel[maxn],ccc;
struct lim {
    int i,j,k,x;
}d[maxn];
map<pair<pi,int>,int>mp;
int nd(int x,int y,int op){
    if(!mp.count(m_p(m_p(x,y),op)))return mp[m_p(m_p(x,y),op)]=++ct;
    return mp[m_p(m_p(x,y),op)];
}
void ins(int x,int y){
    ++ect;nxt[ect]=hd[x],to[ect]=y,hd[x]=ect;
}
void dfs(int u){
    dfn[u]=low[u]=++cc,stk[++tp]=u,instk[u]=1;
    for(int i=hd[u];i;i=nxt[i]){
        int x=to[i];
        if(!dfn[x])dfs(x),low[u]=min(low[u],low[x]);
        else if(instk[x])low[u]=min(low[u],dfn[x]);
    }if(dfn[u]==low[u]){
        ++ccc;
        while(tp){
            int x=stk[tp--];
            instk[x]=0,bel[x]=ccc;
            if(x==u)break;
        }
    }
}
void get(int a,int b,int c,int x){
    ins(nd(a,x,0),nd(b,x,1)),ins(nd(a,x,0),nd(c,x,1));
    ins(nd(a,nx(a,x),1),nd(b,nx(b,x),0)),ins(nd(a,nx(a,x),1),nd(c,nx(c,x),0));
    //g[nd(a,x,0)].p_b(nd(b,x,1)),g[nd(a,x,0)].p_b(nd(c,x,1));
    //g[nd(a,nx(a,x),1)].p_b(nd(b,nx(b,x),0)),g[nd(a,nx(a,x),1)].p_b(nd(c,nx(c,x),0));
}
int f[maxn];
void slv(){
    n=read(),m=read();
    up(i,1,m){
        int a=read(),b=read(),c=read(),x=read();
        d[i].i=a,d[i].j=b,d[i].k=c,d[i].x=x;
        st[a].insert(x),st[b].insert(x),st[c].insert(x);
    }up(i,1,n)st[i].insert(int(1e9+1));
    up(i,1,m){
        int a=d[i].i,b=d[i].j,c=d[i].k,x=d[i].x;
        get(a,b,c,x),get(b,a,c,x),get(c,a,b,x);
    }up(i,1,n)for(int x:st[i])nd(i,x,0),nd(i,x,1);
    up(i,1,n){
        for(auto it=++st[i].begin();it!=st[i].end();++it){
            int x=(*it);it--;int y=(*it);it++;
            //g[nd(i,x,1)].p_b(nd(i,y,1)),g[nd(i,y,0)].p_b(nd(i,x,0));
            ins(nd(i,x,1),nd(i,y,1)),ins(nd(i,y,0),nd(i,x,0));
        }
    }
    up(i,1,ct)if(!dfn[i])dfs(i);
    up(i,1,n)for(int x:st[i])if(bel[nd(i,x,0)]==bel[nd(i,x,1)]){
        printf("NO\n");return;
    }printf("YES\n");
    up(i,1,n){
        int res=-1,lst=-1;
        for(int x:st[i]){
            int a=nd(i,x,0),b=nd(i,x,1);
            if(bel[a]<bel[b]){res=lst;break;}
            lst=x;
        }f[i]=max(res,1);
    }up(i,1,m){
        int a=d[i].i,b=d[i].j,c=d[i].k,x=d[i].x;
        ll w=(ll)f[a]+f[b]+f[c]-max({f[a],f[b],f[c]})-min({f[a],f[b],f[c]});
        assert(w==x);
    }up(i,1,n)printf("%d ",f[i]);
}
int main(){
    //freopen("1.in","r",stdin),freopen("1.out","w",stdout);
    //int t=read();while(t--)slv();
    slv();
    return 0;
}
//(i,x,1)->(i,pre(x),1) (i,x,0)->(i,nxt(x),0)

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 11ms
memory: 106288kb

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: 20
Accepted
time: 12ms
memory: 106292kb

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: 20
Accepted
time: 15ms
memory: 106280kb

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 1 385329352 866319564 

result:

ok solution is correct

Test #4:

score: 20
Accepted
time: 9ms
memory: 106176kb

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: 20
Accepted
time: 19ms
memory: 106220kb

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: 20
Accepted
time: 9ms
memory: 106224kb

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

result:

ok solution is correct

Test #7:

score: 20
Accepted
time: 7ms
memory: 104256kb

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

result:

ok solution is correct

Test #8:

score: 20
Accepted
time: 4ms
memory: 104256kb

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 1 1 

result:

ok solution is correct

Subtask #2:

score: 10
Accepted

Test #9:

score: 10
Accepted
time: 42ms
memory: 105136kb

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
Accepted
time: 401ms
memory: 119516kb

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:

YES
325002529 459824851 295082589 415323204 815182959 942276740 478735558 111467584 372443066 865933468 870762944 436881726 849916477 838601559 30644239 942276740 236051181 278519554 906172939 46182451 284349661 777302867 514711056 91113251 393446574 393984539 410013534 478037910 848158501 839985283...

result:

ok solution is correct

Test #11:

score: 10
Accepted
time: 478ms
memory: 120208kb

input:

85 98770
27 63 76 248029292
25 30 35 550251757
48 53 54 313065504
4 25 37 610144939
74 75 85 456600945
21 75 79 276185205
8 11 84 490843403
19 42 64 531946207
16 30 81 443517377
8 50 68 108297273
51 53 83 535689817
20 35 74 550251757
3 10 63 602682982
3 41 75 456600945
59 77 83 737132984
27 55 71 24...

output:

YES
796868158 907723685 602682982 100984224 318471625 51502508 180796805 966425090 966425090 943508228 357852673 16220061 575720344 557367888 70281602 16220061 660516746 70390628 944390058 569820119 276185205 238004487 825967092 790137066 879681171 158633329 242047823 823251516 499099426 443517377 7...

result:

ok solution is correct

Test #12:

score: 10
Accepted
time: 471ms
memory: 117468kb

input:

85 98770
20 22 67 732656342
25 44 56 244626385
13 59 75 213697467
63 82 85 309272560
28 57 72 364782312
5 8 30 645939411
23 44 53 376754743
12 34 66 506119701
52 54 70 781735421
8 32 71 569597003
13 34 54 476762429
26 47 66 240658437
7 67 69 496620269
23 30 62 647373465
2 10 44 120620033
13 47 60 49...

output:

YES
853072217 84893870 84893870 744163096 645939411 830618471 496620269 496620269 200930742 120620033 380324990 506119701 49183774 530359747 530359747 718404242 606967479 113270399 861487950 175117549 732656342 732656342 376754743 244626385 244626385 240658437 464279351 364782312 54073243 647373465 ...

result:

ok solution is correct

Test #13:

score: 10
Accepted
time: 446ms
memory: 116584kb

input:

85 98770
21 32 83 503624580
20 39 69 305307880
44 45 57 876818763
10 25 41 522952359
19 62 71 613955167
54 63 74 177973416
6 61 71 360070176
51 52 60 541361998
13 33 46 503624580
2 43 73 68833128
12 55 63 459648386
45 66 67 521097301
29 45 76 307722318
2 19 43 82263839
37 62 69 193456165
54 62 77 53...

output:

YES
32323329 32323329 253295445 836531158 836531158 360070176 175567178 175567178 441708705 441708705 668511993 459648386 459648386 459648386 343676539 410730179 613955167 613955167 613955167 613955167 70655797 70655797 70655797 70655797 522952359 522952359 1538604 1538604 1538604 1538604 1538604 50...

result:

ok solution is correct

Test #14:

score: 10
Accepted
time: 474ms
memory: 119892kb

input:

85 98770
3 50 73 299752403
7 73 74 248077845
11 21 55 567953112
28 46 59 812646150
50 62 66 428307066
12 15 70 328727493
28 38 61 734761219
1 12 18 301543584
40 41 42 154591206
34 50 67 782539441
6 46 54 694114842
17 68 72 600618593
35 56 78 735071616
29 80 82 392386527
26 29 32 332472714
1 63 67 78...

output:

NO

result:

ok no solution

Test #15:

score: 10
Accepted
time: 418ms
memory: 119936kb

input:

85 98770
1 62 71 588317506
24 43 47 363838243
40 75 84 470529263
3 13 70 380819035
29 38 65 429982001
37 72 82 441727959
11 13 77 218506970
22 39 65 768340659
45 60 67 522712319
1 18 29 429982000
9 42 79 344491484
34 54 81 538619513
11 39 75 161544337
37 49 80 344491484
59 61 73 454057625
17 18 28 3...

output:

NO

result:

ok no solution

Subtask #3:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #16:

score: 30
Accepted
time: 21ms
memory: 109040kb

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

result:

ok solution is correct

Test #17:

score: 30
Accepted
time: 15ms
memory: 107188kb

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: 30
Accepted
time: 24ms
memory: 109040kb

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 1 554132482 370764537 905142170 166672290 404755886 364522781 732938991 188181844 240197885 458153570 411373341 635296228 801254851 851220356 393414923 253720282 886695682 643346815 1 794870892 705435825 942112175 480960502 739916080 681118387 96806151 420...

result:

ok solution is correct

Test #19:

score: 30
Accepted
time: 14ms
memory: 106864kb

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: 30
Accepted
time: 20ms
memory: 107004kb

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 1 725814201 465222052 554351793 757386571 554351793 290177907 465222052 164869035 774812229 578945293 725814201 574834092 1 508474159 527586554 465222052 475145071 574834092 854236804 757386571 508474159 164869035 305048016 508663785 225265468 859103011 1 78406158...

result:

ok solution is correct

Test #21:

score: 30
Accepted
time: 15ms
memory: 107084kb

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: 30
Accepted
time: 16ms
memory: 107028kb

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 565431434 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: 30
Accepted
time: 24ms
memory: 107044kb

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 483096393 187474183 2317...

result:

ok solution is correct

Test #24:

score: 30
Accepted
time: 15ms
memory: 106884kb

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: 30
Accepted
time: 20ms
memory: 106900kb

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
Time Limit Exceeded

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #26:

score: 0
Time Limit Exceeded

input:

100000 100000
81017 10545 55789 799774881
62032 98611 26850 622879245
3899 20450 37728 411720977
93833 22867 66256 400655546
99733 95937 76629 869108615
42977 7684 86924 766643875
92542 5317 44655 804443432
40897 86851 13377 394123873
69459 57362 2359 451550287
93737 83595 69209 670362145
45236 2844...

output:


result: