QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#801888 | #9840. Tree Partition | rotcar07 | WA | 518ms | 735376kb | C++23 | 2.5kb | 2024-12-07 10:30:51 | 2024-12-07 10:30:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int mod=998244353,N=2e5+5,M=405;
inline void red(int&x){x>=mod&&(x-=mod);}
int n,k;
vector<int> e[N];int fa[N];
void dfs(int p,int f){fa[p]=f;for(int x:e[p]) if(x!=f) dfs(x,p);}
vector<int> L[N];
int nxt[N],pre[N],cnt[N];
int dp[N][M];
main(){
std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=1,u,v;i<n;i++) cin>>u>>v,e[u].push_back(v),e[v].push_back(u);
dfs(1,0);
for(int i=1;i<=n;i++) if(fa[i]>i) L[fa[i]].push_back(i);
vector<pair<int,vector<int>>>A,B;
for(int i=0;i<=n+1;i++) nxt[i]=i+1,pre[i]=i-1;
A.emplace_back(-1,vector<int>(k+1,0));B.emplace_back(-1,vector<int>(k+1,0));
A.emplace_back(0,vector<int>(k+1,0));A.back().second[0]=1;dp[0][0]=1;
auto upd=[&](auto&A,int p){
A.emplace_back(p,A.back().second);
for(int i=0;i<=k;i++)red(A.back().second[i]+=dp[p][i]);
};set<int> s;
for(int i=1;i<=n;i++){
if(fa[i]<i){
vector<int> w;int T=0;
for(int p=pre[i];p>=fa[i];p=pre[p]){
cnt[p]++;
if(cnt[p]==1) w.push_back(p);
else{
T++;
nxt[pre[p]]=nxt[p];
pre[nxt[p]]=pre[p];
}
}
while(T--) B.pop_back();
reverse(w.begin(),w.end());
for(int x:w) A.pop_back(),upd(B,x);
}else s.insert(i);
auto cmp=[&](const auto&x,const auto&y){return x.first<y.first;};
for(int z:L[i]) s.erase(z);
int fi=0,se=0;
if(!s.empty()){
fi=*s.rbegin();
if(s.size()>1) se=*prev(prev(s.end()));
}
// cout<<fi<<" "<<se<<' '<<B.size()<<' '<<A.size()<<'\n';
// for(auto w:B){
// cout<<w.first<<' ';
// for(int z:w.second) cout<<z<<' ';cout<<'\n';
// }
// cout<<"???\n";
// for(auto w:A){
// cout<<w.first<<' ';
// for(int z:w.second) cout<<z<<' ';cout<<'\n';
// }
auto it=prev(lower_bound(B.begin(),B.end(),make_pair(fi,vector<int>()),cmp));
// cout<<it-B.begin()<<"??!!!?\n";
for(int j=1;j<=k;j++) red(dp[i][j]=B.back().second[j-1]+mod-it->second[j-1]);
it=prev(lower_bound(A.begin(),A.end(),make_pair(se,vector<int>()),cmp));
auto jt=prev(upper_bound(A.begin(),A.end(),make_pair(fi,vector<int>()),cmp));
for(int j=1;j<=k;j++) red(dp[i][j]+=jt->second[j-1]-it->second[j-1]+mod);
upd(A,i);
// for(int j=0;j<=k;j++) cout<<dp[i][j]<<' ';cout<<'\n';
// cout<<"____________\n";
}
for(int i=1;i<=k;i++) cout<<dp[n][i]<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9688kb
input:
4 3 1 2 2 3 2 4
output:
1 2 2
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5952kb
input:
7 7 2 5 3 6 4 5 5 1 1 6 6 7
output:
1 1 0 0 1 2 1
result:
ok 7 lines
Test #3:
score: 0
Accepted
time: 115ms
memory: 666364kb
input:
200000 20 1 2 1 3 1 4 6 5 6 7 6 8 12 9 12 10 12 11 13 14 13 15 13 16 20 17 20 18 20 19 21 22 21 23 21 24 21 25 1 13 6 13 12 13 20 13 21 13 27 26 27 28 27 29 32 30 32 31 32 33 34 35 34 36 34 37 38 39 38 40 38 41 43 42 43 44 43 45 46 47 46 48 46 49 46 50 27 38 32 38 34 38 43 38 46 38 51 52 51 53 51 54...
output:
1 13 176 2319 30068 384955 4875560 61165940 760811301 405332244 246475419 554163687 400425475 668396606 125703386 89953555 995149440 774574469 541392385 429619985
result:
ok 20 lines
Test #4:
score: 0
Accepted
time: 89ms
memory: 666384kb
input:
200000 20 4 1 4 2 4 3 5 6 5 7 5 8 9 10 9 11 9 12 13 14 13 15 13 16 18 17 18 19 18 20 22 21 22 23 22 24 22 25 4 13 5 13 9 13 18 13 22 13 29 26 29 27 29 28 30 31 30 32 30 33 37 34 37 35 37 36 39 38 39 40 39 41 42 43 42 44 42 45 49 46 49 47 49 48 49 50 29 39 30 39 37 39 42 39 49 39 53 51 53 52 53 54 57...
output:
1 14 185 2404 30814 390564 4902418 61000454 752983100 242139987 472863106 929714703 119782922 593712683 609125416 872539629 83372963 639293742 622266226 792288795
result:
ok 20 lines
Test #5:
score: 0
Accepted
time: 55ms
memory: 666068kb
input:
200000 20 1 2 1 3 1 4 8 5 8 6 8 7 9 10 9 11 9 12 16 13 16 14 16 15 19 17 19 18 19 20 24 21 24 22 24 23 24 25 1 16 8 16 9 16 19 16 24 16 27 26 27 28 27 29 33 30 33 31 33 32 36 34 36 35 36 37 39 38 39 40 39 41 45 42 45 43 45 44 46 47 46 48 46 49 46 50 27 39 33 39 36 39 45 39 46 39 53 51 53 52 53 54 57...
output:
1 12 158 2033 25819 324544 4044421 50013717 614106750 503048605 961357590 169415689 710064641 320301852 756985177 967742311 374036652 941058124 588191422 810964435
result:
ok 20 lines
Test #6:
score: 0
Accepted
time: 72ms
memory: 666248kb
input:
200000 20 4 1 4 2 4 3 8 5 8 6 8 7 9 10 9 11 9 12 15 13 15 14 15 16 17 18 17 19 17 20 22 21 22 23 22 24 22 25 4 15 8 15 9 15 17 15 22 15 28 26 28 27 28 29 33 30 33 31 33 32 36 34 36 35 36 37 39 38 39 40 39 41 44 42 44 43 44 45 47 46 47 48 47 49 47 50 28 39 33 39 36 39 44 39 47 39 51 52 51 53 51 54 58...
output:
1 14 185 2408 30925 392609 4934344 61457495 759192354 323633583 518118990 62869842 461787830 235002280 820524864 245863891 813843155 518367835 237965261 480206392
result:
ok 20 lines
Test #7:
score: 0
Accepted
time: 90ms
memory: 666376kb
input:
200000 20 1 2 1 3 1 4 5 6 5 7 5 8 12 9 12 10 12 11 13 14 13 15 13 16 19 17 19 18 19 20 21 22 21 23 21 24 21 25 1 13 5 13 12 13 19 13 21 13 28 26 28 27 28 29 30 31 30 32 30 33 34 35 34 36 34 37 38 39 38 40 38 41 45 42 45 43 45 44 48 46 48 47 48 49 48 50 28 38 30 38 34 38 45 38 48 38 52 51 52 53 52 54...
output:
1 12 162 2139 27808 356888 4528437 56878811 707911548 751808398 222054974 279791496 166135229 747401538 76231320 784949109 746019826 344226740 417885502 996177574
result:
ok 20 lines
Test #8:
score: 0
Accepted
time: 109ms
memory: 671412kb
input:
200000 20 2 1 2 3 2 4 2 5 10 6 10 7 10 8 10 9 14 11 14 12 14 13 14 15 17 16 17 18 17 19 17 20 24 21 24 22 24 23 24 25 26 27 26 28 26 29 26 30 33 31 33 32 33 34 33 35 36 37 36 38 36 39 36 40 45 41 45 42 45 43 45 44 47 46 47 48 47 49 47 50 55 51 55 52 55 53 55 54 58 56 58 57 58 59 58 60 64 61 64 62 64...
output:
1 6 32 163 801 3828 17892 82166 372001 1665172 7387818 32555111 142719061 623206098 716382056 798032235 111522191 907324205 649183234 711010078
result:
ok 20 lines
Test #9:
score: 0
Accepted
time: 83ms
memory: 674140kb
input:
200000 20 2 1 3 4 5 6 7 8 10 9 11 12 14 13 15 16 18 17 20 19 21 22 23 24 25 26 27 28 30 29 31 32 34 33 36 35 38 37 40 39 41 42 44 43 45 46 47 48 49 50 52 51 54 53 55 56 57 58 59 60 62 61 64 63 66 65 67 68 70 69 72 71 74 73 75 76 78 77 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 96 95 97 98 100 9...
output:
1 6 28 123 525 2208 9163 37593 152795 616275 2469825 9844142 39045545 154178384 606270389 378274962 284370698 119748351 103605835 50887914
result:
ok 20 lines
Test #10:
score: 0
Accepted
time: 79ms
memory: 674384kb
input:
200000 20 1 2 4 3 6 5 7 8 10 9 12 11 14 13 15 16 17 18 19 20 22 21 23 24 25 26 28 27 30 29 31 32 33 34 36 35 38 37 39 40 42 41 43 44 46 45 47 48 50 49 52 51 53 54 55 56 58 57 60 59 61 62 64 63 66 65 68 67 70 69 71 72 73 74 75 76 78 77 79 80 82 81 84 83 85 86 88 87 90 89 91 92 94 93 95 96 97 98 99 10...
output:
1 5 25 115 508 2190 9251 38406 157199 636331 2554240 10189169 40463651 160179875 632664753 498284531 840893370 717575251 148116836 172090581
result:
ok 20 lines
Test #11:
score: 0
Accepted
time: 67ms
memory: 672004kb
input:
200000 20 467 400 467 401 467 402 467 403 467 404 467 405 467 406 467 407 467 408 467 409 467 410 467 411 467 412 467 413 467 414 467 415 467 416 467 417 467 418 467 419 467 420 467 421 467 422 467 423 467 424 467 425 467 426 467 427 467 428 467 429 467 430 467 431 467 432 467 433 467 434 467 435 46...
output:
1 5 22 91 362 1400 5294 19643 71709 258203 919227 3243034 11361294 39589640 137398867 475398158 642761809 662785128 484515930 947390198
result:
ok 20 lines
Test #12:
score: 0
Accepted
time: 84ms
memory: 671552kb
input:
200000 20 455 400 455 401 455 402 455 403 455 404 455 405 455 406 455 407 455 408 455 409 455 410 455 411 455 412 455 413 455 414 455 415 455 416 455 417 455 418 455 419 455 420 455 421 455 422 455 423 455 424 455 425 455 426 455 427 455 428 455 429 455 430 455 431 455 432 455 433 455 434 455 435 45...
output:
1 5 22 90 351 1326 4904 17878 64521 231108 822900 2915704 10287661 36166071 126730974 442804706 544933029 374157333 646357026 568707420
result:
ok 20 lines
Test #13:
score: 0
Accepted
time: 68ms
memory: 681648kb
input:
200000 20 1 2 2 3 3 4 4 5 6 7 7 8 1 8 9 10 10 11 11 12 12 13 6 13 14 15 15 16 9 16 17 18 18 19 19 20 20 21 14 21 22 23 23 24 24 25 17 25 26 27 27 28 28 29 29 30 22 30 31 32 32 33 33 34 34 35 26 35 36 37 37 38 38 39 31 39 40 41 41 42 42 43 43 44 36 44 45 46 46 47 47 48 48 49 40 49 50 51 51 52 45 52 5...
output:
1 75128 825619948 444091206 829062655 278521469 237815773 597313479 230618480 802373716 773304989 712677613 237839372 746087668 488970002 17171562 966595372 573931325 526227355 786896120
result:
ok 20 lines
Test #14:
score: 0
Accepted
time: 75ms
memory: 681228kb
input:
200000 20 1 2 2 3 4 5 5 6 6 7 1 7 8 9 9 10 10 11 4 11 12 13 13 14 14 15 8 15 16 17 17 18 18 19 19 20 12 20 21 22 22 23 23 24 24 25 16 25 26 27 27 28 28 29 21 29 30 31 31 32 32 33 33 34 26 34 35 36 36 37 37 38 38 39 30 39 40 41 41 42 42 43 35 43 44 45 45 46 46 47 47 48 40 48 49 50 50 51 51 52 44 52 5...
output:
1 74924 810314840 300962407 478589319 917569974 956848093 997993685 610439861 464664111 727916732 379581436 628134845 967956923 510293112 232570299 200815218 68195908 282199335 336981800
result:
ok 20 lines
Test #15:
score: 0
Accepted
time: 80ms
memory: 680028kb
input:
200000 20 1 2 2 3 3 4 4 5 6 7 7 8 1 8 9 10 10 11 11 12 12 13 6 13 14 15 15 16 16 17 9 17 18 19 19 20 20 21 14 21 22 23 23 24 24 25 18 25 26 27 27 28 22 28 29 30 30 31 31 32 26 32 33 34 34 35 35 36 36 37 29 37 38 39 39 40 40 41 41 42 33 42 43 44 44 45 38 45 46 47 47 48 48 49 43 49 50 51 51 52 52 53 5...
output:
1 74816 802229102 87574505 650723285 656771309 903210078 759853062 497829574 934167620 19659044 378226331 541156973 747002420 518657516 877052886 534925663 978847677 544335234 759285585
result:
ok 20 lines
Test #16:
score: 0
Accepted
time: 84ms
memory: 680908kb
input:
200000 20 1 2 2 3 3 4 5 6 6 7 7 8 1 8 9 10 10 11 11 12 12 13 5 13 14 15 15 16 16 17 17 18 9 18 19 20 20 21 21 22 22 23 14 23 24 25 25 26 26 27 19 27 28 29 29 30 30 31 31 32 24 32 33 34 34 35 35 36 28 36 37 38 38 39 33 39 40 41 41 42 42 43 37 43 44 45 45 46 46 47 47 48 40 48 49 50 50 51 51 52 44 52 5...
output:
1 75374 844131479 167760448 888082583 609134201 948617932 153572706 178975301 328051520 73388765 85180514 272758077 330693357 607354014 41138540 352388304 181035418 700179830 380818871
result:
ok 20 lines
Test #17:
score: 0
Accepted
time: 75ms
memory: 681348kb
input:
200000 20 1 2 2 3 3 4 4 5 6 7 7 8 1 8 9 10 10 11 6 11 12 13 13 14 14 15 15 16 9 16 17 18 18 19 19 20 20 21 12 21 22 23 23 24 24 25 25 26 17 26 27 28 28 29 29 30 22 30 31 32 32 33 33 34 27 34 35 36 36 37 31 37 38 39 39 40 35 40 41 42 42 43 43 44 38 44 45 46 46 47 47 48 41 48 49 50 50 51 45 51 52 53 5...
output:
1 75199 830956574 357426492 112509948 195018850 421113770 193411448 335077876 377273995 475470289 268270822 77011129 165741977 462738002 565429706 856897182 215648623 387452734 155908406
result:
ok 20 lines
Test #18:
score: 0
Accepted
time: 83ms
memory: 669664kb
input:
200000 20 1 2 3 4 6 5 7 8 10 9 12 11 1 7 3 7 6 7 10 7 12 7 13 14 15 16 17 18 19 20 22 21 24 23 13 19 15 19 17 19 22 19 24 19 26 25 27 28 30 29 31 32 33 34 35 36 26 31 27 31 30 31 33 31 35 31 38 37 40 39 42 41 43 44 46 45 47 48 38 43 40 43 42 43 46 43 47 43 49 50 52 51 54 53 56 55 57 58 59 60 49 56 5...
output:
1 25022 313037746 326143902 549774611 529251151 305780838 871118941 935396901 480994057 69357038 565079041 586295267 211954109 885697920 760727702 378813144 362368839 436168000 934195921
result:
ok 20 lines
Test #19:
score: 0
Accepted
time: 72ms
memory: 669660kb
input:
200000 20 1 2 4 3 5 6 7 8 9 10 11 12 1 7 4 7 5 7 9 7 11 7 13 14 16 15 17 18 19 20 21 22 24 23 13 19 16 19 17 19 21 19 24 19 26 25 27 28 30 29 31 32 33 34 36 35 26 31 27 31 30 31 33 31 36 31 38 37 39 40 41 42 43 44 45 46 48 47 38 43 39 43 41 43 45 43 48 43 50 49 51 52 54 53 55 56 58 57 60 59 50 55 51...
output:
1 24979 311962749 864673370 738256178 859803066 635402830 556545282 855791149 536184113 221223658 204825894 469874837 321756201 125751585 559254761 403551309 409720573 327717032 474698395
result:
ok 20 lines
Test #20:
score: 0
Accepted
time: 84ms
memory: 669908kb
input:
200000 20 1 2 3 4 6 5 8 7 10 9 12 11 1 8 3 8 6 8 10 8 12 8 14 13 15 16 18 17 20 19 22 21 24 23 14 20 15 20 18 20 22 20 24 20 26 25 27 28 29 30 31 32 33 34 35 36 26 31 27 31 29 31 33 31 35 31 38 37 40 39 41 42 43 44 46 45 47 48 38 43 40 43 41 43 46 43 47 43 49 50 51 52 53 54 55 56 57 58 59 60 49 55 5...
output:
1 24966 311638113 804407690 904869492 356159781 168039729 736355042 911503299 220764485 699645233 470237319 608891505 629949150 942729056 635359884 2910092 259962910 472382352 237930444
result:
ok 20 lines
Test #21:
score: 0
Accepted
time: 71ms
memory: 669680kb
input:
200000 20 2 1 4 3 6 5 7 8 9 10 12 11 2 7 4 7 6 7 9 7 12 7 14 13 16 15 18 17 19 20 22 21 23 24 14 19 16 19 18 19 22 19 23 19 26 25 28 27 30 29 31 32 33 34 36 35 26 31 28 31 30 31 33 31 36 31 37 38 40 39 41 42 44 43 45 46 47 48 37 44 40 44 41 44 45 44 47 44 49 50 51 52 54 53 56 55 57 58 59 60 49 56 51...
output:
1 24995 312362533 867853624 113718730 125212677 984396175 115757038 835848249 140165564 289892017 653931404 693769958 908935338 786552055 691399344 607827304 79632108 715392002 843837992
result:
ok 20 lines
Test #22:
score: 0
Accepted
time: 76ms
memory: 669880kb
input:
200000 20 2 1 3 4 6 5 8 7 10 9 12 11 2 8 3 8 6 8 10 8 12 8 13 14 16 15 18 17 20 19 22 21 23 24 13 20 16 20 18 20 22 20 23 20 26 25 27 28 30 29 32 31 34 33 36 35 26 32 27 32 30 32 34 32 36 32 38 37 39 40 42 41 43 44 45 46 47 48 38 43 39 43 42 43 45 43 47 43 50 49 52 51 53 54 55 56 57 58 60 59 50 55 5...
output:
1 24987 312162609 366341775 420189392 785247360 653767722 635540731 467217164 82860127 85151628 795586249 157408413 858298559 578884196 687568581 472309769 355929158 351941926 360039605
result:
ok 20 lines
Test #23:
score: -100
Wrong Answer
time: 518ms
memory: 735376kb
input:
200000 400 1 2 1 3 1 4 6 5 6 7 6 8 12 9 12 10 12 11 13 14 13 15 13 16 20 17 20 18 20 19 21 22 21 23 21 24 21 25 1 13 6 13 12 13 20 13 21 13 27 26 27 28 27 29 32 30 32 31 32 33 34 35 34 36 34 37 38 39 38 40 38 41 43 42 43 44 43 45 46 47 46 48 46 49 46 50 27 38 32 38 34 38 43 38 46 38 51 52 51 53 51 5...
output:
1 13 176 2319 30068 384955 4875560 61165940 760811301 405332244 246475419 554163687 400425475 668396606 125703386 89953555 995149440 774574469 541392385 429619985 153707904 106921164 511299642330 27966986635994 669731266114008 11873651792827855 184118549119840838 2646398560695092254 -680580811789272...
result:
wrong answer 23rd lines differ - expected: '198533594', found: '511299642330'