QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #663856 | #7895. Graph Partitioning 2 | Rosmontispes | WA | 56ms | 6000kb | C++20 | 4.5kb | 2024-10-21 17:55:27 | 2024-10-21 17:55:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int B = 500;
const long long mod = 998244353;
void solve()
{
int n,k;
cin>>n>>k;
vector<vector<int>>adj(n + 1);
vector<int>sz(n + 1);
for(int i = 1;i <= n - 1;i ++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
if(k <= B){
vector<vector<long long>>f(n + 1);
auto dfs = [&](auto && dfs,int x,int fa)->void{
sz[x] = 1;
f[x].resize(2);
f[x][1] = 1;
if(k == 1){
f[x][0] = 1;
}
for(auto v:adj[x]){
if(v == fa)
continue;
dfs(dfs,v,x);
vector<long long>g(min((int)f[x].size() + (int)f[v].size() + 1,k + 1));
for(int i = 0;i < min(k + 1,(int)f[x].size());i ++)
for(int j = 0;j < min(k + 1,(int)f[v].size());j ++){
if(i + j > k + 1)
continue;
if(!i){
if(!j){
g[0] += f[x][0] * f[v][0] % mod;
g[0] %= mod;
}
else
continue;
} else {
if(i + j == k + 1){
g[0] += f[x][i] * f[v][j] % mod;
g[0] %= mod;
} else if(i + j == k){
g[i + j] += f[x][i] * f[v][j] % mod;
g[i + j] %= mod;
if(j){
g[0] += f[x][i] * f[v][j] % mod;
g[0] %= mod;
}
} else {
g[i + j] = f[x][i] * f[v][j] % mod;
}
}
}
swap(f[x],g);
}
};
dfs(dfs,1,0);
cout<<f[1][0]<<"\n";
} else {
vector<vector<long long>>f(n + 1);
auto dfs = [&](auto &&dfs,int x,int fa)->void{
sz[x] = 1;
f[x].resize(2);
f[x][0] = 1;
for(auto v:adj[x]){
if(v == fa)
continue;
dfs(dfs,v,x);
int xmx = sz[x] / k,vmx = sz[v] / k;
vector<long long>g(xmx + vmx + 2);
for(int i = 0;i <= xmx;i ++){
for(int j = 0;j <= vmx;j ++){
int rx = (sz[x] - i * k) % (k + 1);
int ry = (sz[v] - j * k) % (k + 1);
if(rx + ry > k + 1)
continue;
if(!rx){
if(!ry){
g[i + j] += f[x][i] * f[v][j] % mod;
g[i + j] %= mod;
}
else
continue;
} else {
if(rx + ry == k + 1){
g[i + j] += f[x][i] * f[v][j] % mod;
g[i + j] %= mod;
} else if(rx + ry == k){
g[i + j] += f[x][i] * f[v][j] % mod;
g[i + j] %= mod;
if(ry){
g[i + j + 1] += f[x][i] * f[v][j] % mod;
g[i + j + 1] %= mod;
}
} else {
g[i + j] = f[x][i] * f[v][j] % mod;
g[i + j] %= mod;
}
}
}
}
swap(g,f[x]);
sz[x] += sz[v];
}
};
dfs(dfs,1,0);
long long ans = 0;
for(int i = 0;i <= sz[1] / k;i ++){
int rx = (sz[1] - i * k) % (k + 1);
if(rx == 0)
(ans += f[1][i]) %= mod;
}
cout<<ans<<"\n";
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
cin>>T;
while(T --)
solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3848kb
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: 56ms
memory: 6000kb
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 0 0 1 0 0 0 1 0 0 0 0 0 0 140 0 0 0 814 0 6 0 0 2 0 0 612 0 0 0 0 0 0 1 0 0 121 4536 0 0 1718 0 0 0 0 444 0 1908 1813 3 74 0 0 0 46 0 0 0 0 0 0 0 0 0 0 0 1 0 0 239 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 48 0 2 0 0 0 1 364 0 206 0 0 76 0 0 0 0 2 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 1 ...
result:
wrong answer 5th lines differ - expected: '1', found: '0'