QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#303677 | #7895. Graph Partitioning 2 | Loging | WA | 33ms | 10252kb | C++20 | 3.2kb | 2024-01-12 21:06:10 | 2024-01-12 21:06:11 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#include<map>
#include<unordered_map>
#define P 998244353
#define M 100005
using namespace std;
struct E{
int to,nx;
}edge[M<<1];
int tot,head[M];
void Addedge(int a,int b){
edge[++tot].to=b;
edge[tot].nx=head[a];
head[a]=tot;
}
int K;
int fa[M];
int dp[M][350],sz[M],DP[350];
void Add(int &x,int y){
x=(x+y)%P;
}
void dfs1(int now){
// printf("now=%d\n",now);
sz[now]=1;
dp[now][K+1]=dp[now][K]=0;
dp[now][0]=0;
dp[now][1]=1;
for(int i=head[now];i;i=edge[i].nx){
int nxt=edge[i].to;
if(nxt==fa[now])continue;
// printf("nxt=%d\n",nxt);
fa[nxt]=now;
dfs1(nxt);
int sza=min(sz[now],K+1),szb=min(sz[nxt],K+1);
for(int j=0;j<=min(sza+szb,K+1);j++)DP[j]=0;
for(int j=0;j<=sza;j++){
for(int k=0;k<=szb&&j+k<=K+1;k++){
Add(DP[j+k],1ll*dp[now][j]*dp[nxt][k]%P);
}
}
for(int j=0;j<=min(sza+szb,K+1);j++)dp[now][j]=DP[j];
sz[now]+=sz[nxt];
}
Add(dp[now][0],dp[now][K+1]);
Add(dp[now][0],dp[now][K]);
dp[now][K+1]=0;
}
//void dfs2(int now){
// sz[now]=1;
// dp[now][0]=1;
// for(int i=head[now];i;i=edge[i].nx){
// int nxt=edge[i].to;
// if(nxt==fa[now])continue;
// fa[nxt]=now;
// dfs2(nxt);
// int sza=sz[now]/(K+1),szb=sz[nxt]/(K+1),szc=(sz[now]+sz[nxt])/(K+1);
// for(int j=0;j<=szc;j++)DP[j]=0;
// for(int j=0;j<=sza;j++){
// for(int k=0;k<=szb;k++){
// Add(DP[j+k],1ll*dp[now][j]*dp[nxt][k]%P);
// }
// }
// for(int j=0;j<=szc;j++)dp[now][j]=DP[j];
// sz[now]+=sz[nxt];
// }
// for(int i=0;i<=sz[now]/(K+1);i++){
// int res=sz[now]-i*(K+1);
// if(res<K){}
// else if(res==K){
// if(now!=1)Add(dp[now][i],dp[now][i]);
// }else if(res==K+1){
// Add(dp[now][i+1],dp[now][i]);
// dp[now][i]=0;
// }else dp[now][i]=0;
// printf("dp[%d][%d]=%d\n",now,i,dp[now][i]);
// }
//}
unordered_map<int,int>mp[M];
void dfs2(int now){
// printf("now=%d\n",now);
mp[now].clear();
sz[now]=1;
mp[now][1]=1;
for(int i=head[now];i;i=edge[i].nx){
int nxt=edge[i].to;
if(nxt==fa[now])continue;
// printf("nxt=%d\n",nxt);
fa[nxt]=now;
dfs2(nxt);
unordered_map<int,int>tmp;
for(auto it1=mp[now].begin();it1!=mp[now].end();it1++){
for(auto it2=mp[nxt].begin();it2!=mp[nxt].end();it2++){
int cnt=(*it1).first+(*it2).first;
if(cnt>K+1)continue;
int val=1ll*(*it1).second*(*it2).second%P;
if(tmp.find(cnt)==tmp.end())tmp[cnt]=val;
else Add(tmp[cnt],val);
}
}
mp[now]=tmp;
}
if(mp[now].find(K+1)!=mp[now].end()){
if(mp[now].find(0)!=mp[now].end()){
Add(mp[now][0],mp[now][K+1]);
}else mp[now][0]=mp[now][K+1];
}
if(mp[now].find(K)!=mp[now].end()){
if(mp[now].find(0)!=mp[now].end()){
Add(mp[now][0],mp[now][K]);
}else mp[now][0]=mp[now][K];
}
mp[now][K+1]=0;
}
int main(){
int T;
scanf("%d",&T);
for(int step=1;step<=T;step++){
int n;
scanf("%d%d",&n,&K);
tot=0;for(int i=1;i<=n;i++)head[i]=0;
for(int i=1;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
Addedge(a,b);
Addedge(b,a);
}
if(K==1)puts("@");
if(K<=300){
dfs1(1);
printf("%d\n",dp[1][0]);
}else{
dfs2(1);
// if(T==3)puts("@");
printf("%d\n",mp[1][0]);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8592kb
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: 33ms
memory: 10252kb
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 ...
result:
wrong answer 3rd lines differ - expected: '112', found: '@'