QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#865267 | #9840. Tree Partition | Mathew_Miao | RE | 2ms | 10184kb | C++20 | 2.8kb | 2025-01-21 16:21:42 | 2025-01-21 16:21:49 |
Judging History
answer
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<numeric>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+10;
const int MAXM=405;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
int n,m;
int dp[MAXN][MAXM];
basic_string <int> tr[MAXN];
inline void add_edge(int x,int y){
tr[x].push_back(y);
}
int dad[MAXN];
void dfs(int x){
for(int to:tr[x])
{
if(to^dad[x]){
dad[to]=x;
dfs(to);
}
}
}
int top[2];
int st[2][MAXN];
int sum[2][MAXN][MAXM];
inline void push(int t,int p){
top[t]++;
st[t][top[t]]=p;
int*s=sum[t][top[t]];
memcpy(s,sum[t][top[t]-1],sizeof(int)*(m+1));
for(int i=0;i<=m;i++)
{
s[i]+=dp[p-1][i];
(s[i]>=mod)&&(s[i]-=mod);
}
}
inline void add(int p){
while(top[1]&&st[1][top[1]]>=p)
{
top[1]--;
}
basic_string <int> s;
while(top[0]&&st[0][top[0]]>=p)
{
s.push_back(st[0][top[0]]);
top[0]--;
}
reverse(s.begin(),s.end());
for(int x:s)
{
push(1,x);
}
}
int res[MAXM];
inline void qry(int t,int p){
memset(res,0,sizeof(int)*(m+1));
if(st[t][top[t]]<p){
return ;
}
int l=1,r=top[t],mid;
while(l<r)
{
mid=(l+r)>>1;
if(st[t][mid]>=p){
r=mid;
}
else{
l=mid+1;
}
}
for(int i=0;i<=m;i++)
{
res[i]=sum[t][top[t]][i]-sum[t][l-1][i];
(res[i]<0)&&(res[i]+=mod);
}
}
set <int> bac;
inline void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
dfs(1);
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
if(dad[i]>i){
bac.insert(i);
}
for(int p:tr[i])
{
if(p<i&&dad[p]==i){
bac.erase(p);
}
}
for(int j=1;j<=m;j++)
{
dp[i][j]=dp[i-1][j-1];
}
int a=0,b=0;
if(!bac.empty()){
a=*prev(bac.end());
}
else{
if(bac.size()>1){
b=*prev(prev(bac.end()));
}
}
if(dad[i]<i){
add(dad[i]+1);
}
qry(1,a+1);
for(int j=1;j<=m;j++)
{
dp[i][j]+=res[j-1];
(dp[i][j]>=mod)&&(dp[i][j]-=mod);
}
if(b){
qry(0,b+1);
for(int j=1;j<=m;j++)
{
dp[i][j]+=res[j-1];
(dp[i][j]>=mod)&&(dp[i][j]-=mod);
}
qry(0,a+1);
for(int j=1;j<=m;j++)
{
dp[i][j]-=res[j-1];
(dp[i][j]<0)&&(dp[i][j]+=mod);
}
}
push(dad[i]<i,i);
}
for(int i=1;i<=m;i++)
{
printf("%d\n",dp[n][i]);
}
}
signed main(){
#ifdef LOCAL
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
atexit([](){fprintf(stderr,"%.3lfs\n",(double)clock()/CLOCKS_PER_SEC);});
#endif
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10060kb
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: 10184kb
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
Runtime Error
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...