QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#801882 | #9840. Tree Partition | rotcar07 | WA | 127ms | 343192kb | C++23 | 2.5kb | 2024-12-07 10:29:16 | 2024-12-07 10:29:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
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];
int 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: 1ms
memory: 5596kb
input:
4 3 1 2 2 3 2 4
output:
1 2 2
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 7668kb
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: -100
Wrong Answer
time: 127ms
memory: 343192kb
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 640740004 59235978 467536955 332888870 612722928 918121025 55427569 38402530 247560044 261196503
result:
wrong answer 11th lines differ - expected: '246475419', found: '640740004'