Submission #38398944

Source Code Expand

#include <iostream>
#include <vector>
#define MOD 998244353
#define N 5100
using namespace std;
int n, dp[N][2][N], siz[N], tmp[2][N];
vector<int> v[N];
void dfs(int x, int f) {
  dp[x][0][0] = dp[x][1][1] = siz[x] = 1;
  for (auto to : v[x]) {
    if (to == f)
      continue;
    dfs(to, x);
    memset(tmp, 0, sizeof(tmp));
    for (int i = 0; i <= siz[x]; i++)
      for (int j = 0; j <= siz[to]; j++)
        for (int k = 0; k <= 1; k++)
          for (int l = 0; l <= 1; l++) {
            if (dp[x][k][i] && dp[to][l][j]) {
              tmp[k][i + j - (l && k)] = (1ll * dp[x][k][i] * dp[to][l][j] +
                                          tmp[k][i + j - (l && k)]) %
                                         MOD;
            }
          }
    memcpy(dp[x], tmp, sizeof(tmp));
    siz[x] += siz[to];
  }
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b), v[b].push_back(a);
  }
  dfs(1, 1);
  for (int i = 1; i <= n; i++) {
    cout << (dp[1][0][i] + dp[1][1][i]) % MOD << '\n';
  }
  return 0;
}

Submission Info

Submission Time
Task F - Components
User swiftc
Language C++ (Clang 10.0.0)
Score 500
Code Size 1145 Byte
Status AC
Exec Time 213 ms
Memory 202924 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 54
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_srnd_00.txt, 01_srnd_01.txt, 01_srnd_02.txt, 01_srnd_03.txt, 01_srnd_04.txt, 01_srnd_05.txt, 01_srnd_06.txt, 01_srnd_07.txt, 02_rnd_00.txt, 02_rnd_01.txt, 02_rnd_02.txt, 02_rnd_03.txt, 02_rnd_04.txt, 02_rnd_05.txt, 02_rnd_06.txt, 02_rnd_07.txt, 03_path_00.txt, 03_path_01.txt, 03_path_02.txt, 03_path_03.txt, 04_star_00.txt, 04_star_01.txt, 04_star_02.txt, 04_star_03.txt, 05_caterpillar_00.txt, 05_caterpillar_01.txt, 05_caterpillar_02.txt, 05_caterpillar_03.txt, 05_caterpillar_04.txt, 05_caterpillar_05.txt, 05_caterpillar_06.txt, 05_caterpillar_07.txt, 05_caterpillar_08.txt, 05_caterpillar_09.txt, 05_caterpillar_10.txt, 05_caterpillar_11.txt, 05_caterpillar_12.txt, 05_caterpillar_13.txt, 06_bintree_00.txt, 06_bintree_01.txt, 06_bintree_02.txt, 06_bintree_03.txt, 06_bintree_04.txt, 06_bintree_05.txt, 06_bintree_06.txt, 06_bintree_07.txt, 07_sqrt_00.txt, 07_sqrt_01.txt, 07_sqrt_02.txt, 07_sqrt_03.txt, 08_one_00.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 9 ms 3360 KiB
00_sample_01.txt AC 2 ms 3280 KiB
00_sample_02.txt AC 3 ms 3404 KiB
01_srnd_00.txt AC 2 ms 3392 KiB
01_srnd_01.txt AC 2 ms 3308 KiB
01_srnd_02.txt AC 2 ms 3528 KiB
01_srnd_03.txt AC 3 ms 3560 KiB
01_srnd_04.txt AC 3 ms 3572 KiB
01_srnd_05.txt AC 3 ms 3796 KiB
01_srnd_06.txt AC 3 ms 3800 KiB
01_srnd_07.txt AC 4 ms 3740 KiB
02_rnd_00.txt AC 134 ms 122908 KiB
02_rnd_01.txt AC 137 ms 122372 KiB
02_rnd_02.txt AC 134 ms 121780 KiB
02_rnd_03.txt AC 132 ms 122376 KiB
02_rnd_04.txt AC 136 ms 122780 KiB
02_rnd_05.txt AC 136 ms 121332 KiB
02_rnd_06.txt AC 137 ms 123184 KiB
02_rnd_07.txt AC 135 ms 123864 KiB
03_path_00.txt AC 208 ms 202888 KiB
03_path_01.txt AC 195 ms 202852 KiB
03_path_02.txt AC 206 ms 202904 KiB
03_path_03.txt AC 213 ms 202924 KiB
04_star_00.txt AC 105 ms 43316 KiB
04_star_01.txt AC 108 ms 43516 KiB
04_star_02.txt AC 136 ms 102864 KiB
04_star_03.txt AC 137 ms 103436 KiB
05_caterpillar_00.txt AC 140 ms 122332 KiB
05_caterpillar_01.txt AC 160 ms 140636 KiB
05_caterpillar_02.txt AC 174 ms 141196 KiB
05_caterpillar_03.txt AC 180 ms 156084 KiB
05_caterpillar_04.txt AC 164 ms 123128 KiB
05_caterpillar_05.txt AC 164 ms 149616 KiB
05_caterpillar_06.txt AC 169 ms 198236 KiB
05_caterpillar_07.txt AC 170 ms 200108 KiB
05_caterpillar_08.txt AC 174 ms 200920 KiB
05_caterpillar_09.txt AC 149 ms 123156 KiB
05_caterpillar_10.txt AC 161 ms 149744 KiB
05_caterpillar_11.txt AC 166 ms 198212 KiB
05_caterpillar_12.txt AC 167 ms 200148 KiB
05_caterpillar_13.txt AC 169 ms 200996 KiB
06_bintree_00.txt AC 138 ms 123016 KiB
06_bintree_01.txt AC 138 ms 122856 KiB
06_bintree_02.txt AC 110 ms 101236 KiB
06_bintree_03.txt AC 108 ms 101360 KiB
06_bintree_04.txt AC 108 ms 101420 KiB
06_bintree_05.txt AC 109 ms 101264 KiB
06_bintree_06.txt AC 108 ms 101264 KiB
06_bintree_07.txt AC 111 ms 101444 KiB
07_sqrt_00.txt AC 104 ms 46080 KiB
07_sqrt_01.txt AC 109 ms 45600 KiB
07_sqrt_02.txt AC 105 ms 45512 KiB
07_sqrt_03.txt AC 106 ms 45292 KiB
08_one_00.txt AC 2 ms 3264 KiB