QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#737362	#7895. Graph Partitioning 2	Andeviking	RE	0ms	3560kb	C++20	3.3kb	2024-11-12 15:37:28	2024-11-12 15:37:42

Judging History

你现在查看的是最新测评结果

[2024-11-12 15:37:42]
评测

测评结果：RE
用时：0ms
内存：3560kb

查看

[2024-11-12 15:37:28]
提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MOD = 998244353;

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<vector<int>> node(n + 1);
    for (int i = 1; i <= n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        node[u].push_back(v);
        node[v].push_back(u);
    }
    int sq = 500;
    if (k <= sq) {
        vector<vector<ll>> dp(n + 1, vector<ll>(k + 2));
        vector<int> sz(n + 1);
        function<void(int, int)> dfs = [&](int x, int f) {
            dp[x][1] = 1;
            sz[x] = 1;
            for (auto e : node[x]) {
                if (e == f)
                    continue;
                vector<ll> ndp(k + 2);
                dfs(e, x);
                for (int i = 0; i <= min(k + 1, sz[e]); ++i) {
                    for (int j = 0; j <= min(k + 1, sz[x]); ++j) {
                        if (i + j > k + 1)
                            continue;
                        ndp[i + j] += dp[e][i] * dp[x][j] % MOD;
                    }
                }

                sz[x] += sz[e];
                for (int i = 0; i <= min(k + 1, sz[x]); ++i)
                    ndp[i] %= MOD;
                swap(dp[x], ndp);
            }
            dp[x][0] = (dp[x][k] + dp[x][k + 1]) % MOD;
            return;
        };
        dfs(1, 0);
        cout << dp[1][0] << '\n';
    }
    else {
        vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(n / k + 1, vector<ll>(2)));
        vector<int> sz(n + 1);
        function<void(int, int)> dfs = [&](int x, int f) {
            sz[x] = 1;
            dp[x][0][0] = 1;
            for (auto e : node[x]) {
                if (e == f)
                    continue;
                vector<vector<ll>> ndp(n / k + 1, vector<ll>(2));
                dfs(e, x);
                for (int i = 0; i <= sz[e] / k; ++i) {
                    for (int j = 0; j <= sz[x] / k; ++j) {
                        for (int b1 = 0; b1 < 2; ++b1) {
                            for (int b2 = 0; b2 < 2; ++b2) {
                                int rem = (sz[e] - i * k) % (k + 1) + (sz[x] - j * k) % (k + 1) + (b1 + b2) * (k + 1);
                                if (rem > k + 1)
                                    continue;
                                ndp[i + j][rem == k + 1] += dp[e][i][b1] * dp[x][j][b2] % MOD;
                            }
                        }
                    }
                }
                sz[x] += sz[e];
                for (int i = 0; i <= sz[e] / k + sz[x] / k; ++i) {
                    ndp[i][0] %= MOD;
                    ndp[i][1] %= MOD;
                }
                swap(dp[x], ndp);
            }
            for (int i = 0; i <= n / k; ++i) {
                (dp[x][i][0] += dp[x][i][1]) %= MOD;
                if ((sz[x] - k * i) % (k + 1) == k)
                    (dp[x][i + 1][0] += dp[x][i][0]) %= MOD;
            }
            return;
        };
        dfs(1, 0);
        ll ans = 0;
        for (int i = 0; i <= n / k; ++i) {
            if ((n - i * k) % (k + 1) == 0)
                (ans += dp[1][i][0]) %= MOD;
        }
        cout << ans << '\n';
    }
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3560kb

input:

output:

2
1

result:

ok 2 lines

Test #2:

score: -100

Runtime Error

input:

output: