QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #639045 | #7895. Graph Partitioning 2 | Forza_Ferrari | WA | 32ms | 13128kb | C++14 | 4.4kb | 2024-10-13 17:45:18 | 2024-10-13 17:45:18 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int block=400,mod=998244353;
int t,n,m;
vector<int> v[100001];
inline void init()
{
ios::sync_with_stdio(0);
cin.tie(0);
}
inline int read()
{
int x;
cin>>x;
return x;
}
inline int Mod(int x)
{
return x>=mod? x-mod:x;
}
namespace sub1
{
int dp[100001][405],s[100001];
inline void dfs(int k,int f)
{
dp[k][1]=s[k]=1;
int tmp[405];
for(int i:v[k])
{
if(i==f)
continue;
dfs(i,k);
s[k]+=s[i];
for(int j=0;j<=m+1;++j)
{
tmp[j]=dp[k][j];
dp[k][j]=0;
}
for(int l=0;l<=m+1;++l)
if(tmp[l])
for(int r=0;l+r<=m+1;++r)
if(dp[i][r])
dp[k][l+r]=Mod(dp[k][l+r]+1ll*tmp[l]*dp[i][r]%mod);
}
dp[k][0]=Mod(dp[k][m]+dp[k][m+1]);
dp[k][m+1]=0;
}
inline void main()
{
for(int i=1;i<=n;++i)
{
s[i]=0;
for(int j=0;j<=m+1;++j)
dp[i][j]=0;
}
dfs(1,0);
cout<<dp[1][0]<<'\n';
}
}
namespace sub2
{
bool flag;
int dp[100001][255][2],s[100001],w[100001];
inline void dfs(int k,int f)
{
s[k]=dp[k][0][0]=1;
int pos=0,tmp[255];
for(int i:v[k])
{
if(i==f)
continue;
dfs(i,k);
s[k]+=s[i];
if(!(w[i]*m<=s[i]&&s[i]<=w[i]*(m+1)))
if(!pos)
pos=i;
else
pos=-1;
for(int j=0;j<=w[k];++j)
{
tmp[j]=dp[k][j][0];
dp[k][j][0]=0;
}
for(int l=0;l<=w[k];++l)
if(tmp[l])
for(int r=0;r<=w[i];++r)
if(dp[i][r][0])
dp[k][l+r][0]=Mod(dp[k][l+r][0]+1ll*tmp[l]*dp[i][r][0]%mod);
w[k]+=w[i];
}
/*if(s[k]/m>w[k]+1)
flag=0;*/
if(s[k]/m==w[k]+1)
if(w[k]*m<=s[k]&&s[k]<=w[k]*(m+1))
{
dp[k][s[k]%m][1]=dp[k][s[k]%m][0];
dp[k][s[k]%m][0]=Mod(dp[k][s[k]%m][0]+dp[k][s[k]%m-1][0]);
dp[k][s[k]%m-1][0]=0;
}
/*else
flag=0;*/
w[k]=s[k]/m;
if(pos!=-1)
{
int sum=0;
vector<int> pre,nxt;
pre.emplace_back(1);
nxt.emplace_back(1);
for(int i:v[k])
{
if(i==f)
continue;
sum+=s[i]%m;
int val=pre.back();
pre.emplace_back(1ll*val*dp[i][s[i]%m][0]%mod);
}
pre.emplace_back(0);
reverse(v[k].begin(),v[k].end());
for(int i:v[k])
{
if(i==f)
continue;
sum+=s[i]%m;
int val=nxt.back();
nxt.emplace_back(1ll*val*dp[i][s[i]%m][0]%mod);
}
nxt.emplace_back(0);
reverse(nxt.begin(),nxt.end());
reverse(v[k].begin(),v[k].end());
int now=0;
for(int i:v[k])
{
if(i==f)
continue;
++now;
if(!pos||i==pos)
dp[k][sum-s[i]%m+1][0]=Mod(dp[k][sum-s[i]%m+1][0]+1ll*pre[now-1]*nxt[now+1]%mod*dp[i][s[i]%m][1]%mod);
}
}
}
inline void main()
{
flag=1;
for(int i=1;i<=n;++i)
{
s[i]=w[i]=0;
for(int j=0;j<=n/m;++j)
dp[i][j][0]=dp[i][j][1]=0;
}
dfs(1,0);
cout<<(flag? dp[1][n/m][0]:0)<<'\n';
}
}
int main()
{
init();
t=read();
while(t--)
{
n=read(),m=read();
for(int i=1;i<=n;++i)
v[i].clear();
for(int i=1;i<n;++i)
{
int x=read(),y=read();
v[x].emplace_back(y);
v[y].emplace_back(x);
}
if(m<=block)
sub1::main();
else
sub2::main();
}
cout.flush();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 9448kb
input:
2 8 2 1 2 3 1 4 6 3 5 2 4 8 5 5 7 4 3 1 2 1 3 2 4
output:
2 1
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 32ms
memory: 13128kb
input:
5550 13 4 10 3 9 1 10 8 3 11 8 5 10 7 9 6 13 5 9 7 2 7 5 12 4 8 8 2 4 1 3 4 7 8 2 5 6 7 4 8 2 3 11 1 11 10 1 4 9 10 8 4 3 6 5 7 6 1 10 2 11 7 11 1 17 2 14 16 13 15 17 3 15 11 1 6 13 2 13 17 4 8 14 10 8 14 14 5 9 12 14 2 12 17 17 6 15 7 14 6 2 14 2 13 2 4 8 4 3 11 7 3 14 1 11 9 13 3 5 10 6 8 3 10 14 ...
output:
0 3 112 0 1 0 1 0 0 0 1 0 1 0 0 1 0 140 0 0 0 814 1 6 1 1 2 2 0 612 0 1 0 0 0 1 1 0 0 121 4536 0 0 1718 0 0 1 0 444 1 1908 1813 3 74 0 1 0 46 0 0 0 0 0 0 0 0 0 1 0 1 1 1 239 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0 48 0 2 0 0 0 1 364 0 206 0 0 76 0 1 0 0 2 0 1 2 0 0 1 0 0 4 0 1 1 0 0 1 1 1 0 0 1 1 ...
result:
wrong answer 5509th lines differ - expected: '1', found: '0'